idnits 2.17.1 draft-ietf-pim-sm-v2-new-02.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 901 instances of too long lines in the document, the longest one being 8 characters in excess of 72. == There are 4 instances of lines with multicast IPv4 addresses in the document. If these are generic example addresses, they should be changed to use the 233.252.0.x range defined in RFC 5771 == There are 1 instance of lines with non-RFC3849-compliant IPv6 addresses in the document. If these are example addresses, they should be changed. ** The document seems to lack a both a reference to RFC 2119 and the recommended RFC 2119 boilerplate, even if it appears to use RFC 2119 keywords. RFC 2119 keyword, line 3684: '...Option SHOULD be included in every Hel...' RFC 2119 keyword, line 3690: '...r (GenID) Option SHOULD be included in...' RFC 2119 keyword, line 3695: '...ut that neighbor SHOULD be discarded a...' RFC 2119 keyword, line 3801: '... A PIM router MUST support the stat...' RFC 2119 keyword, line 3828: '...gured or learned MUST be a domain-wide...' (18 more instances...) Miscellaneous warnings: ---------------------------------------------------------------------------- == Using lowercase 'not' together with uppercase 'MUST', 'SHALL', 'SHOULD', or 'RECOMMENDED' is not an accepted usage according to RFC 2119. Please use uppercase 'NOT' together with RFC 2119 keywords (if that is what you mean). Found 'MUST not' in this paragraph: no Combination is not allowed by the protocol and MUST not be | generated by a router. | == Using lowercase 'not' together with uppercase 'MUST', 'SHALL', 'SHOULD', or 'RECOMMENDED' is not an accepted usage according to RFC 2119. Please use uppercase 'NOT' together with RFC 2119 keywords (if that is what you mean). Found 'SHOULD not' in this paragraph: ? Combination not expected by the protocol, but well-defined. A | router MAY accept it but SHOULD not generate it. | == Using lowercase 'not' together with uppercase 'MUST', 'SHALL', 'SHOULD', or 'RECOMMENDED' is not an accepted usage according to RFC 2119. Please use uppercase 'NOT' together with RFC 2119 keywords (if that is what you mean). Found 'MUST not' in this paragraph: There is an exception with group sets that contain a (*,G) Join source | list entry. The group set expresses the routers interest in receiving | all traffic for the specified group on the shared tree and it MUST | include an (S,G,rpt) Prune source list entry for every source that the | router does not wish to receive. This list of (S,G,rpt) Prune source- | list entries MUST not be split in multiple messages. | -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (2 March 2001) is 8457 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 3268 -- Looks like a reference, but probably isn't: 'Actions A6' on line 2988 -- Looks like a reference, but probably isn't: 'Actions A3' on line 3279 -- Looks like a reference, but probably isn't: 'Actions A2' on line 3291 -- Looks like a reference, but probably isn't: 'Actions A4' on line 3279 -- Looks like a reference, but probably isn't: 'Actions A5' on line 3302 -- Looks like a reference, but probably isn't: 'Optionally' on line 3649 ** Obsolete normative reference: RFC 2283 (ref. '1') (Obsoleted by RFC 2858) == Outdated reference: A later version (-12) exists of draft-ietf-pim-sm-bsr-00 -- Possible downref: Non-RFC (?) normative reference: ref. '5' ** Obsolete normative reference: RFC 2434 (ref. '6') (Obsoleted by RFC 5226) ** Obsolete normative reference: RFC 2401 (ref. '7') (Obsoleted by RFC 4301) ** Obsolete normative reference: RFC 2460 (ref. '8') (Obsoleted by RFC 8200) -- Possible downref: Normative reference to a draft: ref. '9' == Outdated reference: A later version (-02) exists of draft-ietf-pim-simplekmp-01 -- Possible downref: Normative reference to a draft: ref. '10' == Outdated reference: A later version (-04) exists of draft-holbrook-ssm-00 -- Possible downref: Normative reference to a draft: ref. '11' Summary: 9 errors (**), 0 flaws (~~), 9 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-02.txt Mark Handley/ACIRI 4 Hugh Holbrook/Cisco 5 Isidor Kouvelas/Cisco 6 2 March 2001 7 Expires: September 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 . . . . . . . . . . . . . . . . . . . . . . . . 14 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. . . . . . . . . . . . . . . . . . . . . 26 77 4.3.1. Sending Register Messages from the DR . . . . . . . . . . . 26 78 4.3.2. Receiving Register Messages at the RP . . . . . . . . . . . 30 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 . . . . . . . . . . . . 35 82 4.4.3. Receiving (S,G) Join/Prune Messages . . . . . . . . . . . . 39 83 4.4.4. Receiving (S,G,rpt) Join/Prune Messages . . . . . . . . . . 43 84 4.4.5. Sending (*,*,RP) Join/Prune Messages. . . . . . . . . . . . 48 85 4.4.6. Sending (*,G) Join/Prune Messages . . . . . . . . . . . . . 53 86 4.4.7. Sending (S,G) Join/Prune Messages . . . . . . . . . . . . . 57 87 4.4.8. (S,G,rpt) Periodic Messages . . . . . . . . . . . . . . . . 62 88 4.4.9. State Machine for (S,G,rpt) Triggered 89 Messages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 90 4.5. PIM Assert Messages. . . . . . . . . . . . . . . . . . . . . . 67 91 4.5.1. (S,G) Assert Message State Machine. . . . . . . . . . . . . 67 92 4.5.2. (*,G) Assert Message State Machine. . . . . . . . . . . . . 74 93 4.5.3. Assert Metrics. . . . . . . . . . . . . . . . . . . . . . . 80 94 4.5.4. AssertCancel Messages . . . . . . . . . . . . . . . . . . . 82 95 4.5.5. Assert State Macros . . . . . . . . . . . . . . . . . . . . 82 96 4.6. Designated Routers (DR) and Hello Messages . . . . . . . . . . 84 97 4.6.1. Sending Hello Messages. . . . . . . . . . . . . . . . . . . 84 98 4.6.2. DR Election . . . . . . . . . . . . . . . . . . . . . . . . 85 99 4.7. PIM Bootstrap and RP Discovery . . . . . . . . . . . . . . . . 87 100 4.7.1. Group-to-RP Mapping . . . . . . . . . . . . . . . . . . . . 88 101 4.7.2. Hash Function . . . . . . . . . . . . . . . . . . . . . . . 89 102 4.8. Source-Specific Multicast. . . . . . . . . . . . . . . . . . . 90 103 4.8.1. Protocol Modifications for SSM destination 104 addresses. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 105 4.8.2. PIM-SSM-only Routers. . . . . . . . . . . . . . . . . . . . 91 107 4.9. PIM Packet Formats . . . . . . . . . . . . . . . . . . . . . . 92 108 4.9.1. Encoded Source and Group Address Formats. . . . . . . . . . 93 109 4.9.2. Hello Message Format. . . . . . . . . . . . . . . . . . . . 96 110 4.9.3. Register Message Format . . . . . . . . . . . . . . . . . . 99 111 4.9.4. Register-Stop Message Format. . . . . . . . . . . . . . . . 100 112 4.9.5. Join/Prune Message Format . . . . . . . . . . . . . . . . . 101 113 4.9.5.1. Group Set Source List Rules. . . . . . . . . . . . . . . 104 114 4.9.5.2. Group Set Fragmentation. . . . . . . . . . . . . . . . . 107 115 4.9.6. Assert Message Format . . . . . . . . . . . . . . . . . . . 108 116 4.10. PIM Timers. . . . . . . . . . . . . . . . . . . . . . . . . . 109 117 4.11. Timer Values. . . . . . . . . . . . . . . . . . . . . . . . . 110 118 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . . . 115 119 5.1. PIM Address Family . . . . . . . . . . . . . . . . . . . . . . 115 120 5.2. PIM Hello Options. . . . . . . . . . . . . . . . . . . . . . . 116 121 6. Security Considerations . . . . . . . . . . . . . . . . . . . . . 116 122 7. Authors' Addresses. . . . . . . . . . . . . . . . . . . . . . . . 116 123 8. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . 117 124 9. References. . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 125 10. Index. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 126 1. Introduction 128 This document specifies a protocol for efficiently routing multicast 129 groups that may span wide-area (and inter-domain) internets. This 130 protocol is called Protocol Independent Multicast - Sparse Mode (PIM-SM) 131 because, although it may use the underlying unicast routing to provide 132 reverse-path information for multicast tree building, it is not 133 dependent on any particular unicast routing protocol. 135 PIM-SM version 2 was originally specified in RFC 2117, and revised in 136 RFC 2362. This document is intended to obsolete RFC 2362, and to 137 correct a number of deficiencies that have been identified with the way 138 PIM-SM was previously specified. As far as possible, this document 139 specifies the same protocol as RFC 2362, and only diverges from the 140 behavior intended by RFC 2362 when the previously specified behavior was 141 clearly incorrect. Routers implemented according to the specification 142 in this document will be able to successfully interoperate with routers 143 implemented according to RFC 2362. 145 2. Terminology 147 In this document, the key words "MUST", "MUST NOT", "REQUIRED", "SHALL", 148 "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and 149 "OPTIONAL" are to be interpreted as described in RFC 2119 and indicate 150 requirement levels for compliant PIM-SM implementations. 152 2.1. Definitions 154 This specification uses a number of terms to refer to the roles of 155 routers participating in PIM-SM. The following terms have special 156 significance for PIM-SM: 158 Rendezvous Point (RP): 159 An RP is a router that has been configured to be used as the root 160 of the non-source-specific distribution tree for a multicast 161 group. Join messages from receivers for a group are sent towards 162 the RP, and data from senders is sent to the RP so that receivers 163 can discover who the senders are, and start to receive traffic 164 destined for the group. 166 Designated Router (DR): 167 A shared-media LAN like Ethernet may have multiple PIM-SM routers 168 connected to it. If the LAN has directly connected hosts, then a 169 single one of these routers, the DR, will act on behalf of those 170 hosts with respect to the PIM-SM protocol. A single DR is elected 171 per LAN using a simple election process. 173 MRIB Multicast Routing Information Base. This is the multicast 174 topology table, which is typically derived from the unicast 175 routing table, or routing protocols such as MBGP that carry 176 multicast-specific topology information. In PIM-SM this is used 177 to make decisions regarding where to forward Join/Prune messages. 179 RPF Neighbor 180 RPF stands for "Reverse Path Forwarding". The RPF Neighbor of a 181 router with respect to an address is the neighbor that the MRIB 182 indicates should be used to forward packets to that address. In 183 the case of a PIM-SM multicast group, the RPF neighbor is the 184 router that a Join message for that group would be directed to, in 185 the absence of modifying Assert state. 187 TIB Tree Information Base. This is the collection of state at a PIM 188 router that has been created by receiving PIM Join/Prune messages, 189 PIM Assert messages, and IGMP information from local hosts. It 190 essentially stores the state of all multicast distribution trees 191 at that router. 193 MFIB Multicast Forwarding Information Base. The TIB holds all the 194 state that is necessary to forward multicast packets at a router. 195 However, although this specification defines forwarding in terms 196 of the TIB, to actually forward packets using the TIB is very 197 inefficient. Instead a real router implementation will normally 198 build an efficient MFIB from the TIB state to perform forwarding. 199 How this is done is implementation-specific, and is not discussed 200 in this document. 202 Upstream 203 Towards the root of the tree. The root of tree may either be the 204 source or the RP depending on the context. 206 Downstream 207 Away from the root of the tree. 209 2.2. Pseudocode Notation 211 We use set notation in several places in this specification. 213 A (+) B 214 is the union of two sets A and B. 216 A (-) B 217 is the elements of set A that are not in set B. 219 NULL 220 is the empty set or list. 222 In addition we use C-like syntax: 224 = denotes assignment of a variable. 226 == denotes a comparison for equality. 228 != denotes a comparison for inequality. 230 Braces { and } are used for grouping. 232 3. PIM-SM Protocol Overview 234 This section provides an overview of PIM-SM behavior. It is intended as 235 an introduction to how PIM-SM works, and is NOT definitive. For the 236 definitive specification, see Section 4. 238 PIM relies on an underlying topology-gathering protocol to populate a 239 routing table with routes. This routing table is called the MRIB or 240 Multicast Routing Information Base. The routes in this table may be 241 taken directly from the unicast routing table, or it may be different 242 and provided by a separate routing protocol such as MBGP [1]. In any 243 event, the routes in the MRIB must represent a multicast-capable path to 244 each subnet. The MRIB is used to determine the path that PIM control 245 messages such as Join messages take to get to the source subnet, and 246 data flows along the reverse path of the Join messages. Thus, in 247 contrast to the unicast RIB where the routes give a path that data 248 packets take to get to each subnet, the MRIB gives reverse-path 249 information, and indicates the path that data packets would take from 250 each subnet to the router that has the MRIB. 252 Like all multicast routing protocols that implement the service model 253 from RFC 1112 [2], PIM-SM must be able to route data packets from 254 sources to receivers without either the sources or receivers knowing a- 255 priori of the existence of the others. This is essentially done in 256 three phases, although as senders and receivers may come and go at any 257 time, all three phases may be occur simultaneously. 259 Phase One: RP Tree 261 In phase one, a multicast receiver expresses its interest in receiving 262 traffic destined for a multicast group. Typically it does this using 263 IGMP [3], but other mechanisms might also serve this purpose. One of 264 the receiver's local routers is elected as the Designated Router (DR) 265 for that subnet. On receiving the receiver's expression of interest, 266 the DR then sends a PIM Join message towards the RP for that multicast 267 group. This Join message is known as a (*,G) Join because it joins 268 group G for all sources to that group. The (*,G) Join travels hop-by- 269 hop towards the RP for the group, and in each router it passes through, 270 multicast tree state for group G is instantiated. Eventually the (*,G) 271 Join either reaches the RP, or reaches a router that already has (*,G) 272 Join state for that group. When many receivers join the group, their 273 Join messages converge on the RP, and form a distribution tree for group 274 G that is rooted at the RP. This is known as the RP Tree (RPT), and is 275 also known as the shared tree because it is shared by all sources 276 sending to that group. Join messages are resent periodically so long as 277 the receiver remains in the group. When all receivers on a leaf-network 278 leave the group, the DR will send a PIM (*,G) Prune message towards the 279 RP for that multicast group. However if the prune message is not sent 280 for any reason, the state will eventually time out. 282 A multicast data sender just starts sending data destined for a 283 multicast group. The sender's local router (DR) takes those data 284 packets, unicast-encapsulates them, and sends them directly to the RP. 285 The RP receives these encapsulated data packets, decapsulates them, and 286 forwards them onto the shared tree. The packets then follow the (*,G) 287 multicast tree state in the routers on the RP Tree, being replicated 288 wherever the RP Tree branches, and eventually reaching all the receivers 289 for that multicast group. The process of encapsulating data packets to 290 the RP is called registering, and the encapsulation packets are known as 291 PIM Register packets. 293 At the end of phase one, multicast traffic is flowing encapsulated to 294 the RP, and then natively over the RP tree to the multicast receivers. 296 Phase Two: Register Stop 298 Register-encapsulation of data packets is inefficient for two reasons: 300 o Encapsulation and decapsulation may be relatively expensive operations 301 for a router to perform, depending on whether or not the router has 302 appropriate hardware for these tasks. 304 o Traveling all the way to the RP, and then back down the shared tree 305 may entail the packets traveling a relatively long distance to reach 306 receivers that are close to the sender. For some applications, this 307 increased latency is undesirable. 309 Although Register-encapsulation may continue indefinitely, for these 310 reasons, the RP will normally choose to switch to native forwarding. To 311 do this, when the RP receives a register-encapsulated data packet from 312 source S on group G, it will normally initiate an (S,G) source-specific 313 Join towards S. This join message travels hop-by-hop towards S, 314 instantiating (S,G) multicast tree state in the routers along the path. 315 (S,G) multicast tree state is used only to forward packets for group G 316 if those packets come from source S. Eventually the Join message 317 reaches S's subnet or a router that already has (S,G) multicast tree 318 state, and then packets from S start to flow following the (S,G) tree 319 state towards the RP. These data packets may also reach routers with 320 (*,G) state along the path towards the RP - if so, they can short-cut 321 onto the RP tree at this point. 323 While the RP is in the process of joining the source-specific tree for 324 S, the data packets will continue being encapsulated to the RP. When 325 packets from S also start to arrive natively at the the RP, the RP will 326 be receiving two copies of each of these packets. At this point, the RP 327 starts to discard the encapsulated copy of these packets, and it sends a 328 Register-Stop message back to S's DR to prevent the DR unnecessarily 329 encapsulating the packets. 331 At the end of phase 2, traffic will be flowing natively from S along a 332 source-specific tree to the RP, and from there along the shared tree to 333 the receivers. Where the two trees intersect, traffic may transfer from 334 the source-specific tree to the RP tree, and so avoid taking a long 335 detour via the RP. 337 It should be noted that a sender may start sending before or after a 338 receiver joins the group, and thus phase two may happen before the 339 shared tree to the receiver is built. 341 Phase 3: Shortest-Path Tree 343 Although having the RP join back towards the source removes the 344 encapsulation overhead, it does not completely optimize the forwarding 345 paths. For many receivers the route via the RP may involve a 346 significant detour when compared with the shortest path from the source 347 to the receiver. 349 To obtain lower latencies, a receiver's DR may optionally initiate a 350 transfer from the shared tree to a source-specific shortest-path tree 351 (SPT). To do this, it issues an (S,G) Join towards S. This 352 instantiates state in the routers along the path to S. Eventually this 353 join either reaches S's subnet, or reaches a router that already has 354 (S,G) state. When this happens, data packets from S start to flow 355 following the (S,G) state until they reach the receiver. 357 At this point the receiver (or a router upstream of the receiver) will 358 be receiving two copies of the data - one from the SPT and one from the 359 RPT. When the first traffic starts to arrive from the SPT, the DR or 360 upstream router starts to drop the packets for G from S that arrive via 361 the RP tree. In addition, it sends an (S,G) prune message towards the 362 RP. This is known as an (S,G,rpt) Prune. The prune message travels 363 hop-by-hop, instantiating state along the path towards the RP indicating 364 that traffic from S for G should NOT be forwarded in this direction. 365 The prune is propagated until it reaches the RP or a router that still 366 needs the traffic from S for other receivers. 368 By now, the receiver will be receiving traffic from S along the 369 shortest-path tree between the receiver and S. In addition, the RP is 370 receiving the traffic from S, but this traffic is no longer reaching the 371 receiver along the RP tree. As far as the receiver is concerned, this 372 is the final distribution tree. 374 Source-specific Joins 376 IGMPv3 permits a receiver to join a group and specify that it only wants 377 to receive traffic for a group if that traffic comes from a particular 378 source. If a receiver does this, and no other receiver on the LAN 379 requires all the traffic for the group, then the DR may omit performing 380 a (*,G) join to set up the shared tree, and instead issue a source- 381 specific (S,G) join only. 383 The range of multicast addresses from 232.0.0.0 to 232.255.255.255 is 384 currently set aside for source-specific multicast in IPv4. For groups 385 in this range, receivers should only issue source-specific IGMPv3 joins. 386 If a PIM router receives a non-source-specific join for a group in this 387 range, it should ignore it, as described in Section 4.8. 389 Source-specific Prunes 391 IGMPv3 also permits a receiver to join a group and specify that it only 392 wants to receive traffic for a group if that traffic does not come from 393 a specific source or sources. In this case, the DR will perform a (*,G) 394 join as normal, but may combine this with an (S,G,rpt) prune for each of 395 the sources the receiver does not wish to receive. 397 Multi-access Transit LANs 399 The overview so far has concerned itself with point-to-point links. 400 However, using multi-access LANs such as Ethernet for transit is not 401 uncommon. This can cause complications for three reasons: 403 o Two or more routers on the LAN may issue (*,G) Joins to different 404 upstream routers on the LAN because they have inconsistent MRIB 405 entries regarding how to reach the RP. Both paths on the RP tree will 406 be set up, causing two copies of all the shared tree traffic to appear 407 on the LAN. 409 o Two or more routers on the LAN may issue (S,G) Joins to different 410 upstream routers on the LAN because they have inconsistent MRIB 411 entries regarding how to reach source S. Both paths on the source- 412 specific tree will be set up, causing two copies of all the traffic 413 from S to appear on the LAN. 415 o A router on the LAN may issue a (*,G) Join to one upstream router on 416 the LAN, and another router on the LAN may issue an (S,G) Join to a 417 different upstream router on the same LAN. Traffic from S may reach 418 the LAN over both the RPT and the SPT. If the receiver behind the 419 downstream (*,G) router doesn't issue an (S,G,rpt) prune, then this 420 condition would persist. 422 All of these problems are caused by there being more than one upstream 423 router with join state for the group or source-group pair. PIM does not 424 prevent such duplicate joins from occurring - instead when duplicate 425 data packets appear on the LAN from different routers, these routers 426 notice this, and then elect a single forwarder. This election is 427 performed using PIM Assert messages, which resolve the problem in favor 428 of the upstream router which has (S,G) state, or if neither or both 429 router has (S,G) state, then in favor of the router with the best metric 430 to the RP for RP trees, or the best metric to the source to source- 431 specific trees. 433 These Assert messages are also received by the downstream routers on the 434 LAN, and these cause subsequent join messages to be sent to the upstream 435 router that won the Assert. 437 RP Discovery 439 PIM-SM routers need to know the address of the RP for each group for | 440 which they have (*,G) state. This address is obtained either through a | 441 bootstrap mechanism or through static configuration. | 443 One dynamic way to do this is to use the Bootstrap Router (BSR) | 444 mechanism [4]. One router in each PIM domain is elected the Bootstrap | 445 Router through a simple election process. All the routers in the domain | 446 that are configured to be candidates to be RPs periodically unicast | 447 their candidacy to the BSR. From the candidates, the BSR picks an RP- | 448 set, and periodically announces this set in a bootstrap message. | 449 Bootstrap messages are flooded hop-by-hop throughout the domain until | 450 all routers in the domain know the RP-Set. | 452 To map a group to an RP, a router hashes the group address into the RP- 453 set using an order-preserving hash function (one that minimizes changes 454 if the RP set changes). The resulting RP is the one that it uses as the 455 RP for that group. 457 4. Protocol Specification 459 The specification of PIM-SM is broken into several parts: 461 o Section 4.1 details the protocol state stored. 463 o Section 4.2 specifies the data packet forwarding rules. 465 o Section 4.3 specifies the PIM Register generation and processing 466 rules. 468 o Section 4.4 specifies the PIM Join/Prune generation and processing 469 rules. 471 o Section 4.5 specifies the PIM Assert generation and processing rules. 473 o Designated Router (DR) election is specified in Section 4.6. 475 o Section 4.7 specifies the RP discovery mechanisms. | 477 o The subset of PIM required to support Source-Specific Multicast, PIM- 478 SSM, is described in Section 4.8. 480 o PIM packet formats are specified in Section 4.9. 482 o A summary of PIM-SM timers and their default values is given in 483 Section 4.10. 485 4.1. PIM Protocol State 487 This section specifies all the protocol state that a PIM implementation 488 should maintain in order to function correctly. We term this state the 489 Tree Information Base or TIB, as it holds the state of all the multicast 490 distribution trees at this router. In this specification we define PIM 491 mechanisms in terms of the TIB. However, only a very simple 492 implementation would actually implement packet forwarding operations in 493 terms of this state. Most implementations will use this state to build 494 a multicast forwarding table, which would then be updated when the 495 relevant state in the TIB changes. 497 Although we specify precisely the state to be kept, this does not mean 498 that an implementation of PIM-SM needs to hold the state in this form. 499 This is actually an abstract state definition, which is needed in order 500 to specify the router's behavior. A PIM-SM implementation is free to 501 hold whatever internal state it requires, and will still be conformant 502 with this specification so long as it results in the same externally 503 visible protocol behavior as an abstract router that holds the following 504 state. 506 We divide TIB state into four sections: 508 (*,*,RP) state 509 State that maintains per-RP trees, for all groups served by a given 510 RP. 512 (*,G) state 513 State that maintains the RP tree for G. 515 (S,G) state 516 State that maintains a source-specific tree for source S and group 517 G. 519 (S,G,rpt) state 520 State that maintains source-specific information about source S on 521 the RP tree for G. For example, if a source is being received on 522 the source-specific tree, it will normally have been pruned off the 523 RP tree. This prune state is (S,G,rpt) state. 525 The state that should be kept is described below. Of course, 526 implementations will only maintain state when it is relevant to 527 forwarding operations - for example, the "NoInfo" state might be assumed 528 from the lack of other state information, rather than being held 529 explicitly. 531 4.1.1. General Purpose State 533 A router holds the following non-group-specific state: 535 For each interface: 537 Neighbor State: 539 For each neighbor: 541 o Information from neighbor's Hello 543 o Neighbor's Gen ID. 545 o Neighbor liveness timer (NLT) 547 Designated Router (DR) State: 549 o Designated Router's IP Address 551 o DR's DR Priority 553 Designated Router state is described in section 4.6. | 555 4.1.2. (*,*,RP) State 557 For every RP a router keeps the following state: 559 (*,*,RP) state: 560 For each interface: 562 PIM (*,*,RP) Join/Prune State: 564 o State: One of {"NoInfo" (NI), "Join" (J), 565 "PrunePending" (PP)} 567 o Prune Pending Timer (PPT) 569 o Join/Prune Expiry Timer (ET) 571 Not interface specific: 573 o Upstream Join/Prune Timer (JT) 575 o Last RPF Neighbor towards RP that was used 577 PIM (*,*,RP) Join/Prune state is the result of receiving PIM (*,*,RP) 578 Join/Prune messages on this interface, and is specified in section 579 4.4.1. 581 The upstream (*,*,RP) Join/Prune timer is used to send out periodic 582 Join(*,*,RP) messages, and to override Prune(*,*,RP) messages from peers 583 on an upstream LAN interface. 585 The last RPF neighbor towards the RP is stored because if the MRIB 586 changes then the RPF neighbor towards the RP may change. If it does so, 587 then we need to trigger a new Join(*,*,RP) to the new upstream neighbor 588 and a Prune(*,*,RP) to the old upstream neighbor. Similarly, if a 589 router detects through a changed GenID in a Hello message that the 590 upstream neighbor towards the RP has rebooted, then it should re- 591 instantiate state by sending a Join(*,*,RP). These mechanisms are 592 specified in Section 4.4.5. 594 4.1.3. (*,G) State 596 For every group G a router keeps the following state: 598 (*,G) state: 599 For each interface: 601 Local Membership: 602 State: One of {"NoInfo", "Include"} 604 PIM (*,G) Join/Prune State: 606 o State: One of {"NoInfo" (NI), "Join" (J), 607 "PrunePending" (PP)} 609 o Prune Pending Timer (PPT) 611 o Join/Prune Expiry Timer (ET) 613 (*,G) Assert Winner State 615 o State: One of {"NoInfo" (NI), "I lost Assert" (L), 616 "I won Assert" (W)} 618 o Assert Timer (AT) 620 o Assert winner's IP Address 622 o Assert winner's Assert Metric 624 Not interface specific: 626 o Upstream Join/Prune Timer (JT) 628 o Last RP Used 630 o Last RPF Neighbor towards RP that was used 632 Local membership is the result of the local membership mechanism (such 633 as IGMP) running on that interface. It need not be kept if this router 634 is not the DR on that interface unless this router won a (*,G) assert on 635 this interface for this group, although implementations may optionally 636 keep this state in case they become the DR or assert winner. This 637 information is used by the pim_include(*,G) macro described in section 638 4.1.6. 640 PIM (*,G) Join/Prune state is the result of receiving PIM (*,G) 641 Join/Prune messages on this interface, and is specified in section 642 4.4.2. The state is used by the macros that calculate the outgoing 643 interface list in section 4.1.6, and in the JoinDesired(*,G) macro 644 (defined in section 4.4.6) that is used in deciding whether a Join(*,G) 645 should be sent upstream. 647 (*,G) Assert Winner state is the result of sending or receiving (*,G) 648 assert messages on this interface. It is specified in section 4.5.2. 650 The upstream (*,G) Join/Prune timer is used to send out periodic 651 Join(*,G) messages, and to override Prune(*,G) messages from peers on an 652 upstream LAN interface. 654 The last RP used must be stored because if the RP Set changes (section 655 4.7) then state must be torn down and rebuilt for groups whose RP 656 changes. 658 The last RPF neighbor towards the RP is stored because if the MRIB 659 changes then the RPF neighbor towards the RP may change. If it does so, 660 then we need to trigger a new Join(*,G) to the new upstream neighbor and 661 a Prune(*,G) to the old upstream neighbor. Similarly, if a router 662 detects through a changed GenID in a Hello message that the upstream 663 neighbor towards the RP has rebooted, then it should re-instantiate 664 state by sending a Join(*,G). These mechanisms are specified in Section 665 4.4.6. 667 4.1.4. (S,G) State 669 For every source/group pair (S,G) a router keeps the following state: 671 (S,G) state: 673 For each interface: 675 Local Membership: 676 State: One of {"NoInfo", "Include"} 678 PIM (S,G) Join/Prune State: 680 o State: One of {"NoInfo" (NI), "Join" (J), 681 "PrunePending" (PP)} 683 o Prune Pending Timer (PPT) 685 o Join/Prune Expiry Timer (ET) 687 (S,G) Assert Winner State 689 o State: One of {"NoInfo" (NI), "I lost Assert" (L), 690 "I won Assert" (W)} 692 o Assert Timer (AT) 694 o Assert winner's IP Address 696 o Assert winner's Assert Metric 698 Not interface specific: 700 o Upstream (S,G) Join/Prune Timer (JT) 702 o Last RPF Neighbor towards S that was used 704 o SPT bit (indicates (S,G) state is active) 706 o (S,G) KeepAlive Timer (KAT) 708 Local membership is the result of the local source-specific membership 709 mechanism (such as IGMP version 3) running on that interface and 710 specifying that this particular source should be included. As stored 711 here, this state is the resulting state after any IGMPv3 inconsistencies 712 have been resolved. It need not be kept if this router is not the DR on 713 that interface unless this router won a (S,G) assert on this interface 714 for this group. This information is used by the pim_include(S,G) macro 715 described in section 4.1.6. 717 PIM (S,G) Join/Prune state is the result of receiving PIM (S,G) 718 Join/Prune messages on this interface, and is specified in section 719 4.4.2. The state is used by the macros that calculate the outgoing 720 interface list in section 4.1.6, and in the JoinDesired(S,G) macro 721 (defined in section 4.4.7) that is used in deciding whether a Join(S,G) 722 should be sent upstream. 724 (S,G) Assert Winner state is the result of sending or receiving (S,G) 725 assert messages on this interface. It is specified in section 4.5.1. 727 The upstream (S,G) Join/Prune timer is used to send out periodic 728 Join(S,G) messages, and to override Prune(S,G) messages from peers on an 729 upstream LAN interface. 731 The last RPF neighbor towards S is stored because if the MRIB changes 732 then the RPF neighbor towards S may change. If it does so, then we need 733 to trigger a new Join(S,G) to the new upstream neighbor and a Prune(S,G) 734 to the old upstream neighbor. Similarly, if the router detects through 735 a changed GenID in a Hello message that the upstream neighbor towards S 736 has rebooted, then it should re-instantiate state by sending a 737 Join(S,G). These mechanisms are specified in Section 4.4.7. 739 The SPTbit is used to indicate whether forwarding is taking place on the 740 (S,G) Shortest Path Tree (SPT) or on the (*,G) tree. A router can have 741 (S,G) state and still be forwarding on (*,G) state during the interval 742 when the source-specific tree is being constructed. When SPTbit is 743 FALSE, only (*,G) forwarding state is used to forward packets from S to 744 G. When SPTbit is TRUE, both (*,G) and (S,G) forwarding state are used. 746 The (S,G) Keepalive Timer is updated by data being forwarded using this 747 (S,G) forwarding state. It is used to keep (S,G) state alive in the 748 absence of explicit (S,G) Joins. Amongst other things, this is 749 necessary for the so-called "turnaround rules" - when the RP uses (S,G) 750 joins to stop encapsulation, and then (S,G) prunes to prevent traffic 751 from unnecessarily reaching the RP. 753 4.1.5. (S,G,rpt) State 755 For every source/group pair (S,G) for which a router also has (*,G) 756 state, it also keeps the following state: 758 (S,G,rpt) state: 760 For each interface: 762 Local Membership: 763 State: One of {"NoInfo", "Exclude"} 765 PIM (S,G,rpt) Join/Prune State: 767 o State: One of {"NoInfo", "Pruned", "PrunePending"} 769 o Prune Pending Timer (PPT) 771 o Join/Prune Expiry Timer (ET) 773 Not interface specific: 775 Upstream (S,G,rpt) Join/Prune State: 777 o State: One of {"NotJoined(*,G)", 778 "NotPruned(S,G,rpt)", "Pruned(S,G,rpt)"} 780 o Override Timer (OT) 782 Local membership is the result of the local source-specific membership 783 mechanism (such as IGMPv3) running on that interface and specifying that 784 although there is (*,G) Include state, this particular source should be 785 excluded. As stored here, this state is the resulting state after any 786 IGMPv3 inconsistencies between LAN members have been resolved. It need 787 not be kept if this router is not the DR on that interface unless this 788 router won a (*,G) assert on this interface for this group. This 789 information is used by the pim_exclude(S,G) macro described in section 790 4.1.6. 792 PIM (S,G,rpt) Join/Prune state is the result of receiving PIM (S,G,rpt) 793 Join/Prune messages on this interface, and is specified in section 794 4.4.4. The state is used by the macros that calculate the outgoing 795 interface list in section 4.1.6, and in the rules for adding 796 Prune(S,G,rpt) messages to Join(*,G) messages specified in section 797 4.4.8. 799 The upstream (S,G,rpt) Join/Prune state is used along with the Override 800 Timer to send the correct override messages in response to Join/Prune 801 messages sent by upstream peers on a LAN. This state and behavior are 802 specified in section 4.4.9. 804 4.1.6. State Summarization Macros 806 Using this state, we define the following "macro" definitions which we 807 will use in the descriptions of the state machines and pseudocode in the 808 following sections. 810 The most important macros are those that define the outgoing interface 811 list (or "olist") for the relevant state. An olist can be "immediate" 812 if it is built directly from the state of the relevant type. For 813 example, the immediate_olist(S,G) is the olist that would be built if 814 the router only had (S,G) state and no (*,G) or (S,G,rpt) state. In 815 contrast, the "inherited" olist inherits state from other types. For 816 example, the inherited_olist(S,G) is the olist that is relevant for 817 forwarding a packet from S to G using both source-specific and group- 818 specific state. 820 There is no immediate_olist(S,G,rpt) as (S,G,rpt) state is negative 821 state - it removes interfaces in the (*,G) olist from the olist that is 822 actually used to forward traffic. The inherited_olist(S,G,rpt) is 823 therefore the olist that would be used for a packet from S to G 824 forwarding on the RP tree. It is a strict subset of 825 immediate_olist(*,G). 827 Generally speaking, the inherited olists are used for forwarding, and 828 the immediate_olists are used to make decisions about state maintenance. 830 immediate_olist(*,*,RP)= 831 joins(*,*,RP) 833 immediate_olist(*,G) = 834 joins(*,G) (+) pim_include(*,G) (-) lost_assert(*,G) 836 immediate_olist(S,G) = 837 joins(S,G) (+) pim_include(S,G) (-) lost_assert(S,G) 839 inherited_olist(S,G,rpt) = 840 ( joins(*,*,RP(G)) (+) joins(*,G) (-) prunes(S,G,rpt) ) 841 (+) ( pim_include(*,G) (-) pim_exclude(S,G)) 842 (-) ( lost_assert(*,G) (+) lost_assert(S,G,rpt) ) 844 inherited_olist(S,G) = 845 inherited_olist(S,G,rpt) (+) immediate_olist(S,G) 847 The macros pim_include(*,G) and pim_include(S,G) indicate the interfaces 848 to which traffic might be forwarded because of hosts that are local 849 members on that interface. Note that normally only the DR cares about 850 local membership, but when an assert happens, the assert winner takes 851 over responsibility for forwarding traffic to local members that have 852 requested traffic on a group or source/group pair. 854 pim_include(*,G) = 855 { all interfaces I such that: 856 ( ( I_am_DR( I ) AND lost_assert(*,G,I) == FALSE ) 857 OR AssertWinner(*,G,I) == me ) 858 AND local_receiver_include(*,G,I) } 860 pim_include(S,G) = 861 { all interfaces I such that: 862 ( (I_am_DR( I ) AND lost_assert(S,G,I) == FALSE ) 863 OR AssertWinner(S,G,I) == me ) 864 AND local_receiver_include(S,G,I) } 866 pim_exclude(S,G) = 867 { all interfaces I such that: 868 ( (I_am_DR( I ) AND lost_assert(S,G,I) == FALSE ) 869 OR AssertWinner(S,G,I) == me ) 870 AND local_receiver_exclude(S,G,I) } 872 The clause "local_receiver_include(S,G,I)" is true if the IGMP module or 873 other local membership mechanism has determined that there are local 874 members on interface I that desire to receive traffic sent specifically 875 by S to G. "local_receiver_include(*,G,I)" is true if the IGMP module 876 or other local membership mechanism has determined that there are local 877 members on interface I that desire to receive all traffic sent to G. 878 "local_receiver_exclude(S,G,I) is true if local_receiver_include(*,G,I) 879 is true but none of the local members desire to receive traffic from S. 881 The set "joins(*,*,RP)" is the set of all interfaces on which the router 882 has received (*,*,RP) Joins: 884 joins(*,*,RP) = 885 { all interfaces I such that 886 DownstreamJPState(*,*,RP,I) is either Joined or 887 PrunePending } 889 DownstreamJPState(*,*,RP,I) is the state of the finite state machine in 890 section 4.4.1. 892 The set "joins(*,G)" is the set of all interfaces on which the router 893 has received (*,G) Joins: 895 joins(*,G) = 896 { all interfaces I such that 897 DownstreamJPState(*,G,I) is either Joined or PrunePending } 899 DownstreamJPState(*,G,I) is the state of the finite state machine in 900 section 4.4.2. 902 The set "joins(S,G)" is the set of all interfaces on which the router 903 has received (S,G) Joins: 905 joins(S,G) = 906 { all interfaces I such that 907 DownstreamJPState(S,G,I) is either Joined or PrunePending } 909 DownstreamJPState(S,G,I) is the state of the finite state machine in 910 section 4.4.3. 912 The set "prunes(S,G,rpt)" is the set of all interfaces on which the 913 router has received (*,G) joins and (S,G,rpt) prunes. 915 prunes(S,G,rpt) = 916 { all interfaces I such that 917 DownstreamJPState(S,G,I) is Pruned or PruneTmp } 919 The set "lost_assert(*,G)" is the set of all interfaces on which the 920 router has received (*,G) joins but has lost a (*,G) assert. The macro 921 lost_assert(*,G,I) is defined in Section 4.5.5. 923 lost_assert(*,G) = 924 { all interfaces I such that 925 lost_assert(*,G,I) == TRUE } 927 The set "lost_assert(S,G,rpt)" is the set of all interfaces on which the 928 router has received (*,G) joins but has lost an (S,G) assert. The macro 929 lost_assert(S,G,rpt,I) is defined in Section 4.5.5. 931 lost_assert(S,G,rpt) = 932 { all interfaces I such that 933 lost_assert(S,G,rpt,I) == TRUE } 935 The set "lost_assert(S,G)" is the set of all interfaces on which the 936 router has received (S,G) joins but has lost an (S,G) assert. The macro 937 lost_assert(S,G,I) is defined in Section 4.5.5. 939 lost_assert(S,G) = 940 { all interfaces I such that 941 lost_assert(S,G,I) == TRUE } 943 The following pseudocode macro definitions are also used in many places 944 in the specification. Basically RPF' is the RPF neighbor towards an RP 945 or source unless a PIM-Assert has overridden the normal choice of 946 neighbor. 948 neighbor RPF'(*,G) { 949 if ( I_Am_Assert_Loser(*,G,RPF_interface(RP(G))) ) { 950 return AssertWinner(*, G, RPF_interface(RP(G)) ) 951 } else { 952 return MRIB.next_hop( RP(G) ) 953 } 954 } 956 neighbor RPF'(S,G,rpt) { 957 if( I_Am_Assert_Loser(S, G, RPF_interface(RP(G)) ) ) { 958 return AssertWinner(S, G, RPF_interface(RP(G)) ) 959 } else { 960 return RPF'(*,G) 961 } 962 } 964 neighbor RPF'(S,G) { 965 if ( I_Am_Assert_loser(S, G, RPF_interface(S) )) { 966 return AssertWinner(S, G, RPF_interface(S) ) 967 } else { 968 return MRIB.next_hop( S ) 969 } 970 } 972 RPF'(*,G) and RPF'(S,G) indicate the neighbor from which data packets 973 should be coming and to which joins should be sent on the RP tree and 974 SPT respectively. 976 RPF'(S,G,rpt) is basically RPF'(*,G) modified by the result of an 977 Assert(S,G) on RPF_interface(RP(G)). In such a case, packets from S 978 will be originating from a different router than RPF'(*,G). If we only 979 have active (*,G) Join state, we need to accept packets from 980 RPF'(S,G,rpt), and add a Prune(S,G,rpt) to the periodic Join(*,G) 981 messages that we send to RPF'(*,G) (See Section 4.4.8). 983 The function MRIB.next_hop( S ) returns the next-hop PIM neighbor toward 984 the host S, as indicated by the current MRIB. If S is directly 985 adjacent, then MRIB.next_hop( S ) returns NULL. At the RP for G, 986 MRIB.next_hop( RP(G )) returns NULL. 988 I_Am_Assert_loser(S, G, I) is true if the Assert start machine (in 989 section 4.5.1) for (S,G) on Interface I is in "I am Assert Loser" state. 991 I_Am_Assert_loser(*, G, I) is true if the Assert start machine (in 992 section 4.5.2) for (*,G) on Interface I is in "I am Assert Loser" state. 994 4.2. Data Packet Forwarding Rules 996 The PIM-SM packet forwarding rules are defined below in pseudocode. 998 iif is the incoming interface of the packet. 999 S is the source address of the packet. 1000 G is the destination address of the packet (group address). 1001 RP is the address of the Rendezvous Point for this group. 1002 RPF_interface(S) is the interface the MRIB indicates would be used 1003 to route packets to S. 1004 RPF_interface(RP) is the interface the MRIB indicates would be used 1005 to route packets to RP, except at the RP when it is the 1006 decapsulation interface (the "virtual" interface on which register 1007 packets are received). 1009 First, we restart (or start) the Keepalive timer if the source is on a 1010 directly connected subnet. 1012 Second, we check to see if the SPT bit should be set because we've now 1013 switched from the RP tree to the SPT. 1015 Next we check to see whether the packet should be accepted based on TIB 1016 state and the interface that the packet arrived on. 1018 If the packet should be forwarded using (S,G) state, we then build an 1019 outgoing interface list for the packet. If this list is not empty, then 1020 we refresh the (S,G) state keepalive timer. 1022 If the packet should be forwarded using (*,*,RP) or (*,G) state, then we 1023 just build an outgoing interface list for the packet. 1025 Finally we remove the incoming interface from the outgoing interface 1026 list we've created, and if the resulting outgoing interface list is not 1027 empty, we forward the packet out of those interfaces. 1029 On receipt on a data from S to G on interface iif: 1031 if( DirectlyConnected(S) == TRUE ) { 1032 set KeepaliveTimer(S,G) to Keepalive_Period 1033 # Note: register state transition may happen as a result 1034 # of restarting KeepaliveTimer, and must be dealt with here. 1035 } 1037 Update_SPTbit(S,G,iif) 1039 if( iif == RPF_interface(S) AND UpstreamJPState(S,G) == Joined ) { 1040 oiflist = inherited_olist(S,G) 1041 if( oiflist != NULL ) { 1042 restart KeepaliveTimer(S,G) 1043 } 1044 } else if( iif == RPF_interface(RP) AND SPTbit(S,G) == FALSE) { 1045 oiflist = inherited_olist(S,G,rpt) 1046 } else { 1047 # Note: RPF check failed 1048 if ( SPTbit(S,G) == TRUE AND iif is in inherited_olist(S,G) ) { 1049 send Assert(S,G) on iif 1050 } else if ( SPTbit(S,G) == FALSE AND 1051 iif is in inherited_olist(S,G,rpt) { 1052 send Assert(*,G) on iif 1053 } 1054 } 1056 oiflist = oiflist (-) iif 1057 forward packet on all interfaces in oiflist 1059 This pseudocode employs several "macro" definitions: 1061 directly_connected(S) is TRUE if the source S is on any subnet that is 1062 directly connected to this router (or for packets originating on this 1063 router). 1065 inherited_olist(S,G) and inherited_olist(S,G,rpt) are defined in Section 1066 4.1. 1068 Basically inherited_olist(S,G) is the outgoing interface list for 1069 packets forwarded on (S,G) state taking into account (*,*,RP) state, 1070 (*,G) state, asserts, etc. 1072 inherited_olist(S,G,rpt) is the outgoing interface for packets forwarded 1073 on (*,*,RP) or (*,G) state taking into account (S,G,rpt) prune state, 1074 and asserts, etc. 1076 Update_SPTbit(S,G,iif) is defined in section 4.2.1. 1078 UpstreamJPState(S,G) is the state of the finite state machine in section 1079 4.4.7. 1081 Keepalive_Period is defined in Section 4.10. 1083 Data triggered PIM-Assert messages sent from the above forwarding code 1084 should be rate-limited in a implementation-dependent manner. 1086 4.2.1. Setting and Clearing the (S,G) SPT bit 1088 The (S,G) SPTbit is used to distinguish whether to forward on 1089 (*,*,RP)/(*,G) or on (S,G) state. When switching from the RP tree to 1090 the source tree, there is a transition period when data is arriving due 1091 to upstream (*,*,RP)/(*,G) state while upstream (S,G) state is being 1092 established during which time a router should continue to forward only 1093 on (*,*,RP)/(*,G) state. This prevents temporary black-holes that would 1094 be caused by sending a Prune(S,G,rpt) before the upstream (S,G) state 1095 has finished being established. 1097 Thus, when a packet arrives, the (S,G) SPTbit is updated as follows: 1099 void 1100 Update_SPTbit(S,G,iif) { 1101 if ( iif == RPF_interface(S) 1102 AND JoinDesired(S,G) == TRUE 1103 AND ( DirectlyConnected(S) == TRUE 1104 OR RPF_interface(S) != RPF_interface(RP) 1105 OR inherited_olist(S,G,rpt) == NULL 1106 OR RPF'(S,G) == RPF'(*,G) ) ) { 1107 Set SPTbit(S,G) to TRUE 1108 } 1109 } 1111 Additionally a router sets SPTbit(S,G) to TRUE when it sees an 1112 Assert(S,G) on RPF_interface(S). 1114 JoinDesired(S,G) is defined in Section 4.4.7, and indicates whether we 1115 have the appropriate (S,G) Join state to wish to send a Join(S,G) 1116 upstream. 1118 Basically Update_SPTbit will set the SPT bit if we have the appropriate 1119 (S,G) join state and the packet arrived on the correct upstream 1120 interface for S, and one or more of the following conditions applies: 1122 1. The source is directly connected, in which case the switch to the 1123 SPT is a no-op. 1125 2. The RPF interface to S is different from the RPF interface to the 1126 RP. The packet arrived on RPF_interface(S), and so the SPT must 1127 have been completed. 1129 3. No-one wants the packet on the RP tree. 1131 4. RPF'(S,G) == RPF'(*,G). In this case the router will never be able 1132 to tell if the SPT has been completed, so it should just switch 1133 immediately. 1135 In the case where the RPF interface is the same for the RP and for S, 1136 but RPF'(S,G) and RPF'(*,G) differ, then we wait for an Assert(S,G) 1137 which indicates that the upstream router with (S,G) state believes the 1138 SPT has been completed. However item (3) above is needed because there 1139 may not be any (*,G) state to trigger an Assert(S,G) to happen. 1141 The SPT bit is cleared in the (S,G) upstream state machine (see Section 1142 4.4.7) when JoinDesired(S,G) becomes FALSE. 1144 4.3. PIM Register Messages 1146 Overview 1148 The Designated Router (DR) on a LAN or point-to-point link encapsulates 1149 multicast packets from local sources to the RP for the relevant group 1150 unless it recently received a Register Stop message for that (S,G) or 1151 (*,G) from the RP. When the DR receives a Register Stop message from 1152 the RP, it starts a Register Stop timer to maintain this state. Just 1153 before the Register Stop timer expires, the DR sends a Null-Register 1154 Message to the RP to allow the RP to refresh the Register Stop 1155 information at the DR. If the Register Stop timer actually expires, the 1156 DR will resume encapsulating packets to the RP. | 1158 4.3.1. Sending Register Messages from the DR 1160 Every PIM-SM router has the capability to be a DR. The state machine 1161 below is used to implement Register functionality. For the purposes of 1162 specification, we represent the mechanism to encapsulate packets to the 1163 RP as a Register-Tunnel interface, which is added to or removed from the 1164 (S,G) olist. The tunnel interface then takes part in the normal packet 1165 forwarding rules specified in Section 4.2. 1167 If register state is maintained, it is maintained only for directly 1168 connected sources, and is per-(S,G). There are four states in the DR's 1169 per-(S,G) Register state-machine: 1171 Join (J) 1172 The register tunnel is "joined" (the join is actually implicit, but 1173 the DR acts as if the RP has joined the DR on the tunnel 1174 interface). 1176 Prune (P) 1177 The register tunnel is "pruned" (this occurs when a Register Stop 1178 is received). 1180 Join Pending (JP) 1181 The register tunnel is pruned but the DR is contemplating adding it 1182 back. 1184 No Info (NI) 1185 No information. This is the initial state, and the state when the 1186 router is not the DR. 1188 In addition, a RegisterStop timer (RST) is kept if the state machine in 1189 not in the No Info state. 1191 +-----------------------------------+ 1192 | Figures omitted from text version | 1193 +-----------------------------------+ 1195 Figure 1: Per-(S,G) register state-machine at a DR 1197 In tabular form, the state-machine is: 1199 +---------+-----------------------------------------------------------------+ 1200 | | Event | 1201 | +------------+--------------+-------------+-----------+-----------+ 1202 Prev StateRegister- CouldRegister CouldRegister Register- RP changed | 1203 | Stop Timer ->True ->False Stop | | 1204 | expires | | received | | 1205 +---------+------------+--------------+-------------+-----------+-----------+ 1206 No Info + +> J state + + + | 1207 (NI) | add tunnel | | | | 1208 +---------+------------+--------------+-------------+-----------+-----------+ 1209 | + + +> NI state +> P state +> J state | 1210 | | | remove tunnel remove redirect | 1211 | | | | tunnel; tunnel to | 1212 Join (J) | | | set new RP; | 1213 | | | | Register- stop | 1214 | | | | Stop Register- | 1215 | | | | timer(*) Stop timer | 1216 +---------+------------+--------------+-------------+-----------+-----------+ 1217 | +> J state + +> NI state +> P state +> J state | 1218 | add tunnel | remove tunnel set redirect | 1219 Join | | | Register- tunnel to | 1220 Pending | | | Stop new RP; | 1221 (JP) | | | timer(*) stop | 1222 | | | | | Register- | 1223 | | | | | Stop timer | 1224 +---------+------------+--------------+-------------+-----------+-----------+ 1225 | +> JP state + +> NI state + +> J state | 1226 | set | remove tunnel | redirect | 1227 | Register- | | | tunnel to | 1228 Prune (P) Stop | | | new RP; | 1229 | timer(**); | | | stop | 1230 | send null | | | Register- | 1231 | register | | | Stop timer | 1232 +---------+------------+--------------+-------------+-----------+-----------+ 1234 Notes: 1236 (*) The RegisterStopTimer is set to a random value chosen uniformly from 1237 the interval ( 0.5 * Register_Suppression_Time, 1.5 * 1238 Register_Suppression_Time) minus Register_Probe_Time; 1240 Subtracting off register_probe_time is a bit unnecessary because it is 1241 really small compared to register suppression timeout, but was in the 1242 old spec and is kept for compatibility. 1244 (**) The RegisterStopTimer is set to register_probe_time. 1246 The macro "CouldRegister" in the state machine is defined as: 1248 Bool CouldRegister(S,G) { 1249 return ( I_am_DR( RPF_interface(S) ) AND 1250 KeepaliveTimer(S,G) is running AND 1251 DirectlyConnected(S) == TRUE ) 1252 } 1254 Note that on reception of a packet at the DR from a directly connected 1255 source, KeepaliveTimer(S,G) needs to be set by the packet forwarding 1256 rules before computing CouldRegister(S,G) in the register state machine, 1257 or the first packet from a source won't be registered. 1259 Encapsulating data packets in the Register Tunnel | 1261 Conceptually, the Register Tunnel is an interface with a smaller MTU | 1262 than the underlying IP interface towards the RP. IP fragmentation on | 1263 packets forwarded on the Register Tunnel is performed based upon this | 1264 smaller MTU. The encapsulating DR may perform Path-MTU Discovery to the | 1265 RP to determine the effective MTU of the tunnel. | 1267 In IPv6, an ICMP Fragmentation Required message may be sent by the | 1268 encapsulating DR. | 1270 Just like any forwarded packet, the TTL of the original data packet is | 1271 decremented before it is encapsulated in the Register Tunnel. | 1273 Handling RegisterStop(*,G) Messages at the DR | 1275 An old RP might send a RegisterStop message with the source address set | 1276 to all-zeros. This was the normal course of action in RFC 2326 when the | 1277 register message matched against (*,G) state at the RP, and was defined 1278 as meaning "stop encapsulating all sources for this group". However, 1279 the behavior of such a RegisterStop(*,G) is ambiguous or incorrect in 1280 some circumstances. 1282 We specify that an RP should not send RegisterStop(*,G) messages, but 1283 for compatibility, a DR should be able to accept one if it is received. 1285 A RegisterStop(*,G) should be treated as a RegisterStop(S,G) for all | 1286 existing (S,G) Register state machines. A router should not apply a 1287 RegisterStop(*,G) to sources that become active after the 1288 RegisterStop(*,G) was received. 1290 4.3.2. Receiving Register Messages at the RP 1292 When an RP receives a Register message, the course of action is decided 1293 according to the following pseudocode: 1295 packet_arrives_on_rp_tunnel( pkt ) { 1296 if( outer.dst is not one of my addresses ) { 1297 drop the packet silently. 1298 # note that this should not happen if the lower layer is working 1299 } 1300 if( I_am_RP( G ) && outer.dst == RP(G) ) { 1301 restart KeepaliveTimer(S,G) 1302 if(( inherited_olist(S,G) == NULL ) OR SPTbit(S,G)) { 1303 send RegisterStop(S,G) to outer.src 1304 } else { 1305 if( ! pkt.NullRegisterBit ) { 1306 decapsulate and pass the inner packet to the normal 1307 forwarding path for forwarding on the (*,G) tree. 1308 } 1309 } 1310 } else { 1311 send RegisterStop(S,G) to outer.src 1312 # Note (*) 1313 } 1314 } 1316 outer.dst is the IP destination address of the encapsulating header. 1318 outer.src is the IP source address of the encapsulating header, i.e., 1319 the DR's address. 1321 I_am_RP(G) is true if the group-to-RP mapping indicates that this router 1322 is the RP for the group. 1324 Note (*): This may block traffic from S for Register_Suppression_Time if 1325 the DR learned about a new group-to-RP mapping before the RP did. 1326 However, this doesn't matter unless we figure out some way for the 1327 RP to also accept (*,G) joins when it doesn't yet realize that it 1328 is about to become the RP for G. This will all get sorted out once 1329 the RP learns the new group-to-rp mapping. We decided to do 1330 nothing about this and just accept the fact that PIM may suffer 1331 interrupted (*,G) connectivity following an RP change. 1333 KeepaliveTimer(S,G) is restarted at the RP when packets arrive on the 1334 proper tunnel interface. This may cause the upstream (S,G) state 1335 machine to trigger a join if the inherited_olist(S,G) is not NULL; 1337 An RP should preserve (S,G) state that was created in response to a 1338 Register message for at least ( 3 * Register_Suppression_Time ), 1339 otherwise the RP may stop joining (S,G) before the DR for S has 1340 restarted sending registers. Traffic would then be interrupted until 1341 the Register-Stop timer expires at the DR. 1343 Thus, at the RP, KeepaliveTimer(S,G) should be restarted to ( 3 * 1344 Register_Suppression_Time + Register_Probe_Time ). | 1346 Just like any forwarded packet, the TTL of the original data packet is | 1347 decremented after it is decapsulated from the Register Tunnel. | 1349 4.4. PIM Join/Prune Messages 1351 A PIM Join/Prune message consists of a list of groups and a list of 1352 Joined and Pruned sources for each group. When processing a received 1353 Join/Prune message, each Joined or Pruned source for a Group is 1354 effectively considered individually, and applies to one or more of the 1355 following state machines. When considering a Join/Prune message whose 1356 PIM Destination field addresses this router, (*,*,RP) Joins and Prunes 1357 can affect the (*,*,RP) and (S,G,rpt) downstream state machines, (*,G) 1358 Joins and Prunes can affect both the (*,G) and (S,G,rpt) downstream 1359 state machines, while (S,G) and (S,G,rpt) Joins and Prunes can only 1360 affect their respective downstream state machines. When considering a 1361 Join/Prune message whose PIM Destination field addresses another router, 1362 most Join or Prune messages could affect each upstream state machine. 1363 (... it's possible to enumerate this ...) XXX 1365 4.4.1. Receiving (*,*,RP) Join/Prune Messages 1367 The per-interface state-machine for receiving (*,*,RP) Join/Prune 1368 Messages is given below. There are three states: 1370 NoInfo (NI) 1371 The interface has no (*,*,RP) Join state and no timers 1372 running. 1374 Join (J) 1375 The interface has (*,*,RP) Join state which will cause us to 1376 forward packets destined for any group handled by RP from this 1377 interface except if there is also (S,G,rpt) prune information 1378 (see Section 4.4.4) or the router lost an assert on this 1379 interface. 1381 PrunePending (PP) 1382 The router has received a Prune(*,*,RP) on this interface from 1383 a downstream neighbor and is waiting to see whether the prune 1384 will be overridden by another downstream router. For 1385 forwarding purposes, the PrunePending state functions exactly 1386 like the Join state. 1388 In addition the state-machine uses two timers: 1390 ExpiryTimer (ET) 1391 This timer is restarted when a valid Join(*,*,RP) is received. 1392 Expiry of the ExpiryTimer causes the interface state to revert 1393 to NoInfo for this group. 1395 PrunePendingTimer (PPT) 1396 This timer is set when a valid Prune(*,*,RP) is received. 1397 Expiry of the PrunePendingTimer causes the interface state to 1398 revert to NoInfo for this group. 1400 +-----------------------------------+ 1401 | Figures omitted from text version | 1402 +-----------------------------------+ 1404 Figure 2: Downstream (*,*,RP) per-interface state-machine 1406 In tabular form, the per-interface (*,*,RP) state-machine is: 1408 +-------------+--------------------------------------------------------+ 1409 | | Event | 1410 | +-------------+--------------+--------------+------------+ 1411 |Prev State |Receive |Receive |Prune |Expiry Timer| 1412 | |Join(*,*,RP) |Prune(*,*,RP) |Pending |Expires | 1413 | | | |Timer | | 1414 | | | |Expires | | 1415 +-------------+-------------+--------------+--------------+------------+ 1416 | |-> J state |-> NI state |- |- | 1417 |NoInfo (NI) |start Expiry | | | | 1418 | |Timer | | | | 1419 +-------------+-------------+--------------+--------------+------------+ 1420 | |-> J state |-> PP state |- |-> NI state | 1421 |Join (J) |restart |start Prune | | | 1422 | |Expiry Timer |Pending Timer | | | 1423 +-------------+-------------+--------------+--------------+------------+ 1424 | |-> J state |-> PP state |-> NI state |-> NI state | 1425 | |restart | |Send Prune- | | 1426 |Prune |Expiry | |Echo(*,*,RP) | | 1427 |Pending (PP) |Timer; stop | | | | 1428 | |Prune | | | | 1429 | |Pending | | | | 1430 | |Timer | | | | 1431 +-------------+-------------+--------------+--------------+------------+ 1433 The transition events "Receive Join(*,*,RP)" and "Receive Prune(*,*,RP)" 1434 imply receiving a Join or Prune targeted to this router's address on the 1435 received interface. If the destination address is not correct, these 1436 state transitions in this state machine must not occur, although seeing 1437 such a packet may cause state transitions in other state machines. 1439 On unnumbered interfaces on point-to-point links, the router's address 1440 should be the same as the source address it chose for the hello packet 1441 it sent over that interface. However on point-to-point links we also 1442 recommend that PIM messages with a 0.0.0.0 destination address are also 1443 accepted. 1445 Transitions from NoInfo State 1447 When in NoInfo state, the following event 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 1454 transitions to the Join state. The Expiry Timer (ET) is 1455 started, and set to the HoldTime from the triggering | 1456 Join/Prune message. | 1458 Transitions from Join State 1460 When in Join state, the following events may trigger a transition: 1462 Receive Join(*,*,RP) 1463 A Join(*,*,RP) is received on interface I with its IP 1464 destination set to the router's address on I. 1466 The (*,*,RP) downstream state machine on interface I remains 1467 in Join state, and the Expiry Timer (ET) is restarted, set to | 1468 maximum of its current value and the HoldTime from the | 1469 triggering Join/Prune message. | 1471 Receive Prune(*,*,RP) 1472 A Prune(*,*,RP) is received on interface I with its IP 1473 destination set to the router's address on I. 1475 The (*,*,RP) downstream state machine on interface I 1476 transitions to the PrunePending state. The PrunePending timer 1477 is started; it is set to the J/P_Override_Interval if the 1478 router has more than one neighbor on that interface; otherwise 1479 it is set to zero causing it to expire immediately. 1481 Expiry Timer Expires 1482 The Expiry Timer for the (*,*,RP) downstream state machine on 1483 interface I expires. 1485 The (*,*,RP) downstream state machine on interface I 1486 transitions to the NoInfo state. 1488 Transitions from PrunePending State 1490 When in PrunePending state, the following events may trigger a 1491 transition: 1493 Receive Join(*,*,RP) 1494 A Join(*,*,RP) is received on interface I with its IP 1495 destination set to the router's address on I. 1497 The (*,*,RP) downstream state machine on interface I 1498 transitions to the Join state. The PrunePending timer is 1499 canceled (without triggering an expiry event). The Expiry | 1500 Timer is restarted, set to maximum of its current value and | 1501 the HoldTime from the triggering Join/Prune message. | 1503 Expiry Timer Expires 1504 The Expiry Timer for the (*,*,RP) downstream state machine on 1505 interface I expires. 1507 The (*,*,RP) downstream state machine on interface I 1508 transitions to the NoInfo state. 1510 PrunePending Timer Expires 1511 The PrunePending Timer for the (*,*,RP) downstream state 1512 machine on interface I expires. 1514 The (*,*,RP) downstream state machine on interface I 1515 transitions to the NoInfo state. A PruneEcho(*,*,RP) is sent 1516 onto the subnet connected to interface I. 1518 The action "Send PruneEcho(*,*,RP)" is triggered when the 1519 router stops forwarding on an interface as a result of a 1520 prune. A PruneEcho(*,*,RP) is simply a Prune(*,*,RP) message 1521 sent by the upstream router to itself on a LAN. By "to | 1522 itself" we mean that the Upstream Neighbor Address field of | 1523 the enclosing Join/Prune message is set to the address of the | 1524 sending router. Its purpose is to add additional reliability | 1525 so that if a Prune that should have been overridden by another | 1526 router is lost locally on the LAN, then the PruneEcho may be 1527 received and cause the override to happen. A 1528 PruneEcho(*,*,RP) need not be sent on a point-to-point 1529 interface. 1531 4.4.2. Receiving (*,G) Join/Prune Messages 1533 When a router receives a Join(*,G) or Prune(*,G) it must first check to 1534 see whether the RP in the message matches RP(G) (the router's idea of 1535 who the RP is). If the RP in the message does not match RP(G) the Join 1536 or Prune should be silently dropped. If a router has no RP information 1537 (e.g. has not recently received a BSR message) then it may choose to 1538 accept Join(*,G) or Prune(*,G) and treat the RP in the message as RP(G). 1540 The per-interface state-machine for receiving (*,G) Join/Prune Messages 1541 is given below. There are three states: 1543 NoInfo (NI) 1544 The interface has no (*,G) Join state and no timers running. 1546 Join (J) 1547 The interface has (*,G) Join state which will cause us to 1548 forward packets destined for G from this interface except if 1549 there is also (S,G,rpt) prune information (see Section 4.4.4) 1550 or the router lost an assert on this interface. 1552 PrunePending (PP) 1553 The router has received a Prune(*,G) on this interface from a 1554 downstream neighbor and is waiting to see whether the prune 1555 will be overridden by another downstream router. For 1556 forwarding purposes, the PrunePending state functions exactly 1557 like the Join state. 1559 In addition the state-machine uses two timers: 1561 ExpiryTimer (ET) 1562 This timer is restarted when a valid Join(*,G) is received. 1563 Expiry of the ExpiryTimer causes the interface state to revert 1564 to NoInfo for this group. 1566 PrunePendingTimer (PPT) 1567 This timer is set when a valid Prune(*,G) is received. Expiry 1568 of the PrunePendingTimer causes the interface state to revert 1569 to NoInfo for this group. 1571 +-----------------------------------+ 1572 | Figures omitted from text version | 1573 +-----------------------------------+ 1575 Figure 3: Downstream (*,G) per-interface state-machine 1577 In tabular form, the per-interface (*,G) state-machine is: 1579 +-------------++--------------------------------------------------------+ 1580 | || Event | 1581 | ++-------------+-------------+-------------+--------------+ 1582 |Prev State ||Receive | Receive | Prune | Expiry Timer | 1583 | ||Join(*,G) | Prune(*,G) | Pending | Expires | 1584 | || | | Timer | | 1585 | || | | Expires | | 1586 +-------------++-------------+-------------+-------------+--------------+ 1587 | ||-> J state | -> NI state | - | - | 1588 |NoInfo (NI) ||start Expiry | | | | 1589 | ||Timer | | | | 1590 +-------------++-------------+-------------+-------------+--------------+ 1591 | ||-> J state | -> PP state | - | -> NI state | 1592 |Join (J) ||restart | start Prune | | | 1593 | ||Expiry Timer | Pending | | | 1594 | || | Timer | | | 1595 +-------------++-------------+-------------+-------------+--------------+ 1596 | ||-> J state | -> PP state | -> NI state | -> NI state | 1597 | ||restart | | Send Prune- | | 1598 |Prune ||Expiry | | Echo(*,G) | | 1599 |Pending (PP) ||Timer; stop | | | | 1600 | ||Prune | | | | 1601 | ||Pending | | | | 1602 | ||Timer | | | | 1603 +-------------++-------------+-------------+-------------+--------------+ 1605 The transition events "Receive Join(*,G)" and "Receive Prune(*,G)" imply 1606 receiving a Join or Prune targeted to this router's address on the 1607 received interface. If the destination address is not correct, these 1608 state transitions in this state machine must not occur, although seeing 1609 such a packet may cause state transitions in other state machines. 1611 On unnumbered interfaces on point-to-point links, the router's address 1612 should be the same as the source address it chose for the hello packet 1613 it sent over that interface. However on point-to-point links we also 1614 recommend that PIM messages with a 0.0.0.0 destination address are also 1615 accepted. 1617 Transitions from NoInfo State 1619 When in NoInfo state, the following event may trigger a transition: 1621 Receive Join(*,G) 1622 A Join(*,G) is received on interface I with its IP destination 1623 set to the router's address on I. 1625 The (*,G) downstream state machine on interface I transitions 1626 to the Join state. The Expiry Timer (ET) is started, and set 1627 to the HoldTime from the triggering Join/Prune message. | 1629 Transitions from Join State 1631 When in Join state, the following events may trigger a transition: 1633 Receive Join(*,G) 1634 A Join(*,G) is received on interface I with its IP destination 1635 set to the router's address on I. 1637 The (*,G) downstream state machine on interface I remains in 1638 Join state, and the Expiry Timer (ET) is restarted, set to | 1639 maximum of its current value and the HoldTime from the | 1640 triggering Join/Prune message. | 1642 Receive Prune(*,G) 1643 A Prune(*,G) is received on interface I with its IP 1644 destination set to the router's address on I. 1646 The (*,G) downstream state machine on interface I transitions 1647 to the PrunePending state. The PrunePending timer is started; 1648 it is set to the J/P_Override_Interval if the router has more 1649 than one neighbor on that interface; otherwise it is set to 1650 zero causing it to expire immediately. 1652 Expiry Timer Expires 1653 The Expiry Timer for the (*,G) downstream state machine on 1654 interface I expires. 1656 The (*,G) downstream state machine on interface I transitions 1657 to the NoInfo state. 1659 Transitions from PrunePending State 1661 When in PrunePending state, the following events may trigger a 1662 transition: 1664 Receive Join(*,G) 1665 A Join(*,G) is received on interface I with its IP destination 1666 set to the router's address on I. 1668 The (*,G) downstream state machine on interface I transitions 1669 to the Join state. The PrunePending timer is canceled 1670 (without triggering an expiry event). The Expiry Timer is | 1671 restarted, set to maximum of its current value and the | 1672 HoldTime from the triggering Join/Prune message. | 1674 Expiry Timer Expires | 1675 The Expiry Timer for the (*,G) downstream state machine on | 1676 interface I expires. | 1678 The (*,G) downstream state machine on interface I transitions | 1679 to the NoInfo state. | 1681 PrunePending Timer Expires | 1682 The PrunePending Timer for the (*,G) downstream state machine | 1683 on interface I expires. | 1685 The (*,G) downstream state machine on interface I transitions | 1686 to the NoInfo state. A PruneEcho(*,G) is sent onto the subnet | 1687 connected to interface I. | 1689 The action "Send PruneEcho(*,G)" is triggered when the router | 1690 stops forwarding on an interface as a result of a prune. A | 1691 PruneEcho(*,G) is simply a Prune(*,G) message sent by the | 1692 upstream router to itself on a LAN. By "to itself" we mean | 1693 that the Upstream Neighbor Address field of the enclosing | 1694 Join/Prune message is set to the address of the sending | 1695 router. Its purpose is to add additional reliability so that | 1696 if a Prune that should have been overridden by another router | 1697 is lost locally on the LAN, then the PruneEcho may be received 1698 and cause the override to happen. A PruneEcho(*,G) need not 1699 be sent on a point-to-point interface. 1701 4.4.3. Receiving (S,G) Join/Prune Messages 1703 The per-interface state machine for receiving (S,G) Join/Prune messages 1704 is given below, and is almost identical to that for (*,G) messages. 1705 There are three states: 1707 NoInfo (NI) 1708 The interface has no (S,G) Join state and no (S,G) timers 1709 running. 1711 Join (J) 1712 The interface has (S,G) Join state which will cause us to 1713 forward packets from S destined for G from this interface if 1714 the (S,G) state is active (the SPTbit is set) except if the 1715 router lost an assert on this interface. 1717 PrunePending (PP) 1718 The router has received a Prune(S,G) on this interface from a 1719 downstream neighbor and is waiting to see whether the prune 1720 will be overridden by another downstream router. For 1721 forwarding purposes, the PrunePending state functions exactly 1722 like the Join state. 1724 In addition there are two timers: 1726 ExpiryTimer (ET) 1727 This timer is set when a valid Join(S,G) is received. Expiry 1728 of the ExpiryTimer causes the interface state to revert to 1729 NoInfo for this group. 1731 PrunePendingTimer (PPT) 1732 This timer is set when a valid Prune(S,G) is received. Expiry 1733 of the PrunePendingTimer causes the interface state to revert 1734 to NoInfo for this group. 1736 +-----------------------------------+ 1737 | Figures omitted from text version | 1738 +-----------------------------------+ 1740 Figure 4: Downstream per-interface (S,G) state-machine 1742 In tabular form, the state machine is: 1744 +-------------++--------------------------------------------------------+ 1745 | || Event | 1746 | ++-------------+-------------+-------------+--------------+ 1747 |Prev State ||Receive | Receive | Prune | Expiry Timer | 1748 | ||Join(S,G) | Prune(S,G) | Pending | Expires | 1749 | || | | Timer | | 1750 | || | | Expires | | 1751 +-------------++-------------+-------------+-------------+--------------+ 1752 | ||-> J state | -> NI state | - | - | 1753 |NoInfo (NI) ||start Expiry | | | | 1754 | ||Timer | | | | 1755 +-------------++-------------+-------------+-------------+--------------+ 1756 | ||-> J state | -> PP state | - | -> NI state | 1757 |Join (J) ||restart | start Prune | | | 1758 | ||Expiry Timer | Pending | | | 1759 | || | Timer | | | 1760 +-------------++-------------+-------------+-------------+--------------+ 1761 | ||-> J state | -> PP state | -> NI state | -> NI state | 1762 | ||restart | | Send Prune- | | 1763 |Prune ||Expiry | | Echo(S,G) | | 1764 |Pending (PP) ||Timer; stop | | | | 1765 | ||Prune | | | | 1766 | ||Pending | | | | 1767 | ||Timer | | | | 1768 +-------------++-------------+-------------+-------------+--------------+ 1770 The transition events "Receive Join(S,G)" and "Receive Prune(S,G)" imply 1771 receiving a Join or Prune targeted to this router's address on the 1772 received interface. If the destination address is not correct, these 1773 state transitions in this state machine must not occur, although seeing 1774 such a packet may cause state transitions in other state machines. 1776 On unnumbered interfaces on point-to-point links, the router's address 1777 should be the same as the source address it chose for the hello packet 1778 it sent over that interface. However on point-to-point links we also 1779 recommend that PIM messages with a 0.0.0.0 destination address are also 1780 accepted. 1782 Transitions from NoInfo State 1784 When in NoInfo state, the following event may trigger a transition: 1786 Receive Join(S,G) 1787 A Join(S,G) is received on interface I with its IP destination 1788 set to the router's address on I. 1790 The (S,G) downstream state machine on interface I transitions 1791 to the Join state. The Expiry Timer (ET) is started, and set 1792 to the HoldTime from the triggering Join/Prune message. | 1794 Transitions from Join State 1796 When in Join state, the following events may trigger a transition: 1798 Receive Join(S,G) 1799 A Join(S,G) is received on interface I with its IP destination 1800 set to the router's address on I. 1802 The (S,G) downstream state machine on interface I remains in 1803 Join state, and the Expiry Timer (ET) is restarted, set to | 1804 maximum of its current value and the HoldTime from the | 1805 triggering Join/Prune message. | 1807 Receive Prune(S,G) 1808 A Prune(S,G) is received on interface I with its IP 1809 destination set to the router's address on I. 1811 The (S,G) downstream state machine on interface I transitions 1812 to the PrunePending state. The PrunePending timer is started; 1813 it is set to the J/P_Override_Interval if the router has more 1814 than one neighbor on that interface; otherwise it is set to 1815 zero causing it to expire immediately. 1817 Expiry Timer Expires 1818 The Expiry Timer for the (S,G) downstream state machine on 1819 interface I expires. 1821 The (S,G) downstream state machine on interface I transitions 1822 to the NoInfo state. 1824 Transitions from PrunePending State 1826 When in PrunePending state, the following events may trigger a 1827 transition: 1829 Receive Join(S,G) 1830 A Join(S,G) is received on interface I with its IP destination 1831 set to the router's address on I. 1833 The (S,G) downstream state machine on interface I transitions 1834 to the Join state. The PrunePending timer is canceled 1835 (without triggering an expiry event). The Expiry Timer is | 1836 restarted, set to maximum of its current value and the | 1837 HoldTime from the triggering Join/Prune message. | 1839 Expiry Timer Expires | 1840 The Expiry Timer for the (S,G) downstream state machine on | 1841 interface I expires. | 1843 The (S,G) downstream state machine on interface I transitions | 1844 to the NoInfo state. | 1846 PrunePending Timer Expires | 1847 The PrunePending Timer for the (S,G) downstream state machine | 1848 on interface I expires. | 1850 The (S,G) downstream state machine on interface I transitions | 1851 to the NoInfo state. A PruneEcho(S,G) is sent onto the subnet | 1852 connected to interface I. | 1854 The action "Send PruneEcho(S,G)" is triggered when the router | 1855 stops forwarding on an interface as a result of a prune. A | 1856 PruneEcho(S,G) is simply a Prune(S,G) message sent by the | 1857 upstream router to itself on a LAN. By "to itself" we mean | 1858 that the Upstream Neighbor Address field of the enclosing | 1859 Join/Prune message is set to the address of the sending | 1860 router. Its purpose is to add additional reliability so that | 1861 if a Prune that should have been overridden by another router | 1862 is lost locally on the LAN, then the PruneEcho may be received 1863 and cause the override to happen. A PruneEcho(S,G) need not 1864 be sent on a point-to-point interface. 1866 4.4.4. Receiving (S,G,rpt) Join/Prune Messages 1868 The per-interface state machine for receiving (S,G,rpt) Join/Prune 1869 messages is given below. There are five states: 1871 NoInfo (NI) 1872 The interface has no (S,G,rpt) Prune state and no (S,G,rpt) 1873 timers running. 1875 Prune (P) 1876 The interface has (S,G,rpt) Prune state which will cause us 1877 not to forward packets from S destined for G from this 1878 interface even though the interface has active (*,G) Join 1879 state. When interface I is in this state, the macro 1880 prune(S,G,rpt,I) returns true. 1882 PrunePending (PP) 1883 The router has received a Prune(S,G,rpt) on this interface 1884 from a downstream neighbor and is waiting to see whether the 1885 prune will be overridden by another downstream router. For 1886 forwarding purposes, the PrunePending state functions exactly 1887 like the NoInfo state. 1889 PruneTmp (P') 1890 This state is a transient state which for forwarding purposes 1891 behaves exactly like the Prune state. A (*,G) Join has been 1892 received (which may cancel the (S,G,rpt) Prune). As we parse 1893 the Join/Prune message from top to bottom, we first enter this 1894 state if the message contains a (*,G) Join. Later in the 1895 message we will normally encounter an (S,G,rpt) prune to re- 1896 instate the Prune state. However if we reach the end of the 1897 message without encountering such a (S,G,rpt) prune, then we 1898 will revert to NoInfo state in this state machine. 1900 As no time is spent in this state, no timers can expire. 1902 PrunePendingTmp (PP') 1903 This state is a transient state which is identical to P' 1904 except that it is associated with the PP state rather than the 1905 P state. For forwarding purposes, PP' behaves exactly like PP 1906 state. 1908 In addition there are two timers: 1910 ExpiryTimer (ET) 1911 This timer is set when a valid Prune(S,G,rpt) is received. 1912 Expiry of the ExpiryTimer causes this state machine to revert 1913 to NoInfo state. 1915 PrunePendingTimer (PPT) 1916 This timer is set when a valid Prune(S,G,rpt) is received. 1917 Expiry of the PrunePendingTimer causes this state machine to 1918 move on to Prune state. 1920 +-----------------------------------+ 1921 | Figures omitted from text version | 1922 +-----------------------------------+ 1924 Figure 5: Downstream per-interface (S,G,rpt) state-machine 1926 In tabular form, the state machine is: 1928 +-------+---------------------------------------------------------------+ 1929 | | Event | 1930 | +----------------+----------+---------+--------+-------+--------+ 1931 |Prev |Receive |Receive Receive |End of |Prune |Expiry | 1932 |State |Join(*,G) |Join Prune |Message |Pending|Timer | 1933 | |or |(S,G,rpt) (S,G,rpt) | |Timer |Expires | 1934 | |Join(*,*,RP(G)) | | | |Expires| | 1935 +-------+----------------+----------+---------+--------+-------+--------+ 1936 | |- |- +> PP |- |n/a |n/a | 1937 | | | state | | | | 1938 | | | start | | | | 1939 | | | Prune | | | | 1940 |No Info| | Pending | | | | 1941 |(NI) | | Timer; | | | | 1942 | | | start | | | | 1943 | | | Expiry | | | | 1944 | | | Timer | | | | 1945 | | | Timer | | | | 1946 +-------+----------------+----------+---------+--------+-------+--------+ 1947 | |-> P' state |-> NI +> P |- |n/a |-> NI | 1948 |Pruned | |state state | | |state | 1949 |(P) | | restart | | | | 1950 | | | Expiry | | | | 1951 | | | Timer | | | | 1952 +-------+----------------+----------+---------+--------+-------+--------+ 1953 |Prune |-> PP' state |-> NI + |- |-> P |n/a | 1954 |Pending| |state | | |state | | 1955 |(PP) | | | | | | | 1956 +-------+----------------+----------+---------+--------+-------+--------+ 1957 | |error |error +> P |-> NI |n/a |n/a | 1958 |Temp. | | state |state | | | 1959 |Pruned | | restart | | | | 1960 |(P') | | Expiry | | | | 1961 | | | Timer | | | | 1962 +-------+----------------+----------+---------+--------+-------+--------+ 1963 |Temp. |error |error +> PP |-> NI |n/a |n/a | 1964 |Prune | | state |state | | | 1965 |Pending| | restart | | | | 1966 |(PP') | | Expiry | | | | 1967 | | | Timer | | | | 1968 +-------+----------------+----------+---------+--------+-------+--------+ 1970 The transition events "Receive Join(S,G,rpt)", "Receive Prune(S,G,rpt)", 1971 "Receive Join(*,G)" and "Receive Join(*,*,RP(G))" imply receiving a Join 1972 or Prune targeted to this router's address on the received interface. 1973 If the destination address is not correct, these state transitions in 1974 this state machine must not occur, although seeing such a packet may 1975 cause state transitions in other state machines. 1977 On unnumbered interfaces on point-to-point links, the router's address 1978 should be the same as the source address it chose for the hello packet 1979 it sent over that interface. However on point-to-point links we also 1980 recommend that PIM messages with a 0.0.0.0 destination address are also 1981 accepted. 1983 Transitions from NoInfo State 1985 When in NoInfo (NI) state, the following event may trigger a transition: 1987 Receive Prune(S,G,rpt) 1988 A Prune(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 the PrunePending state. The Expiry Timer (ET) 1993 is started, and set to the HoldTime from the triggering | 1994 Join/Prune message. The PrunePending timer is started; it is | 1995 set to the J/P_Override_Interval if the router has more than 1996 one neighbor on that interface; otherwise it is set to zero 1997 causing it to expire immediately. 1999 Transitions from PrunePending State 2001 When in PrunePending (PP) state, the following events may trigger a 2002 transition: 2004 Receive Join(*,G) or Join(*,*,RP(G)) 2005 A Join(*,*,RP(G)) or Join(*,G) is received on interface I with 2006 its IP destination set to the router's address on I. 2008 The (S,G,rpt) downstream state machine on interface I 2009 transitions to Temp. PrunePending state whilst the remainder 2010 of the compound Join/Prune message containing the 2011 Join(*,*,RP(G)) or Join(*,G) is processed. 2013 Receive Join(S,G,rpt) 2014 A Join(S,G,rpt) is received on interface I with its IP 2015 destination set to the router's address on I. 2017 The (S,G,rpt) downstream state machine on interface I 2018 transitions to NoInfo state. ET and PPT are canceled. 2020 PrunePending Timer Expires 2021 The PrunePending Timer for the (S,G,rpt) downstream state 2022 machine on interface I expires. 2024 The (S,G,rpt) downstream state machine on interface I 2025 transitions to the Pruned state. 2027 Transitions from Pruned State 2029 When in Pruned (P) state, the following events may trigger a transition: 2031 Receive Join(*,G) or Join(*,*,RP(G)) 2032 A Join(*,*,RP(G)) or Join(*,G) is received on interface I with 2033 its IP destination set to the router's address on I. 2035 The (S,G,rpt) downstream state machine on interface I 2036 transitions to Temp. Pruned state whilst the remainder of the 2037 compound Join/Prune message containing the Join(*,*,RP(G)) or 2038 Join(*,G) is processed. 2040 Receive Join(S,G,rpt) 2041 A Join(S,G,rpt) is received on interface I with its IP 2042 destination set to the router's address on I. 2044 The (S,G,rpt) downstream state machine on interface I 2045 transitions to NoInfo state. ET and PPT are canceled. 2047 Receive Prune(S,G,rpt) 2048 A Prune(S,G,rpt) is received on interface I with its IP 2049 destination set to the router's address on I. 2051 The (S,G,rpt) downstream state machine on interface I remains 2052 in Pruned state. The Expiry Timer (ET) is restarted, set to | 2053 maximum of its current value and the HoldTime from the | 2054 triggering Join/Prune message. | 2056 Expiry Timer Expires 2057 The Expiry Timer for the (S,G,rpt) downstream state machine on 2058 interface I expires. 2060 The (S,G,rpt) downstream state machine on interface I 2061 transitions to the NoInfo state. ET and PPT are canceled. 2063 Transitions from Temp. PrunePending State 2065 When in Temp. PrunePending (PP') state and processing a compound 2066 Join/Prune message, the following events may trigger a transition: 2068 Receive Prune(S,G,rpt) 2069 The compound Join/Prune message contains a Prune(S,G,rpt). 2071 The (S,G,rpt) downstream state machine on interface I 2072 transitions back to the PrunePending state. The Expiry Timer | 2073 (ET) is restarted, set to maximum of its current value and the | 2074 HoldTime from the triggering Join/Prune message. | 2076 End of Message 2077 The end of the compound Join/Prune message is reached. 2079 The (S,G,rpt) downstream state machine on interface I 2080 transitions to the NoInfo state. ET and PPT are canceled. 2082 Transitions from Temp. Pruned State 2084 When in Temp. Pruned (P') state and processing a compound Join/Prune 2085 message, the following events may trigger a transition: 2087 Receive Prune(S,G,rpt) 2088 The compound Join/Prune message contains a Prune(S,G,rpt). 2090 The (S,G,rpt) downstream state machine on interface I 2091 transitions back to the Pruned state. The Expiry Timer (ET) | 2092 is restarted, set to maximum of its current value and the | 2093 HoldTime from the triggering Join/Prune message. | 2095 End of Message 2096 The end of the compound Join/Prune message is reached. 2098 The (S,G,rpt) downstream state machine on interface I 2099 transitions to the NoInfo state. ET and PPT are canceled. 2101 Notes: 2103 Receiving a Prune(*,*,RP(G)) or Prune(*,G) does not affect the (S,G,rpt) 2104 downstream state machine. 2106 4.4.5. Sending (*,*,RP) Join/Prune Messages 2108 The per-interface state-machines for (*,*,RP) hold join state from 2109 downstream PIM routers. This state then determines whether a router 2110 needs to propagate a Join(*,*,RP) upstream towards the RP. 2112 If a router wishes to propagate a Join(*,*,RP) upstream, it must also 2113 watch for messages on its upstream interface from other routers on that 2114 subnet, and these may modify its behavior. If it sees a Join(*,*,RP) to 2115 the correct upstream neighbor, it should suppress its own Join(*,*,RP). 2116 If it sees a Prune(*,*,RP) to the correct upstream neighbor, it should 2117 be prepared to override that prune by sending a Join(*,*,RP) almost 2118 immediately. Finally, if it sees the Generation ID (see Section 4.6) of 2119 the correct upstream neighbor change, it knows that the upstream 2120 neighbor has lost state, and it should be prepared to refresh the state 2121 by sending a Join(*,*,RP) almost immediately. 2123 In addition if the MRIB changes to indicate that the next hop towards 2124 the RP has changed, the router should prune off from the old next hop, 2125 and join towards the new next hop. 2127 The upstream (*,*,RP) state-machine only contains two states: 2129 Not Joined 2130 The downstream state-machines indicate that the router does not 2131 need to join the RP tree for this group. 2133 Joined 2134 The downstream state-machines indicate that the router would like 2135 to join the RP tree for this group. 2137 In addition, one timer JT(*,*,RP) is kept which is used to trigger the 2138 sending of a Join(*,*,RP) to the upstream next hop towards the RP, 2139 MRIB.next_hop(RP). 2141 +-----------------------------------+ 2142 | Figures omitted from text version | 2143 +-----------------------------------+ 2145 Figure 6: Upstream (*,*,RP) state-machine 2147 In tabular form, the state machine is: 2149 +-------------------+---------------------------------------------------+ 2150 | | Event | 2151 | Prev State +--------------------------+------------------------+ 2152 | | JoinDesired(*,*,RP) | JoinDesired(*,*,RP) | 2153 | | ->True | ->False | 2154 +-------------------+--------------------------+------------------------+ 2155 | | -> J state | - | 2156 | NotJoined (NJ) | Send Join(*,*,RP); | | 2157 | | Set Timer to | | 2158 | | t_periodic | | 2159 +-------------------+--------------------------+------------------------+ 2160 | Joined (J) | - | -> NJ state | 2161 | | | Send Prune(*,*,RP) | 2162 +-------------------+--------------------------+------------------------+ 2164 In addition, we have the following transitions which occur within the 2165 Joined state: 2167 +-----------------------------------------------------------------------+ 2168 | In Joined (J) State | 2169 +-----------------+---------------------+-------------------------------+ 2170 | Timer Expires | See | See | 2171 | | Join(*,*,RP) | Prune(*,*,RP) | 2172 | | to | to | 2173 | | MRIB.next_hop(RP) | MRIB.next_hop(RP) | 2174 +-----------------+---------------------+-------------------------------+ 2175 | Send | Increase Timer to | Decrease Timer to | 2176 | Join(*,*,RP); | t_suppressed | t_override | 2177 | Set Timer to | | | 2178 | t_periodic | | | 2179 +-----------------+---------------------+-------------------------------+ 2181 +-----------------------------------------------------------------------+ 2182 | In Joined (J) State | 2183 +-----------------------------------+-----------------------------------+ 2184 | topology change wrt | MRIB.next_hop(RP) GenID | 2185 | MRIB.next_hop(RP) | changes | 2186 +-----------------------------------+-----------------------------------+ 2187 | Send Join(*,*,RP) to new | Decrease Timer to | 2188 | next hop; Send | t_override | 2189 | Prune(*,*,RP) to old | | 2190 | next hop; set Timer to | | 2191 | t_periodic | | 2192 +-----------------------------------+-----------------------------------+ 2193 This state machine uses the following macro: 2195 bool JoinDesired(*,*,RP) { 2196 if immediate_olist(*,*,RP) != NULL 2197 return TRUE 2198 else 2199 return FALSE 2200 } 2202 JoinDesired(*,*,RP) is true when the router has received (*,*,RP) Joins 2203 from any downstream interface. Note that although JoinDesired is true, 2204 the router's sending of a Join(*,*,RP) message may be suppressed by 2205 another router sending a Join(*,*,RP) onto the upstream interface. 2207 Transitions from NotJoined State 2209 When the upstream (*,*,RP) state-machine is in NotJoined state, the 2210 following event may trigger a state transition: 2212 JoinDesired(*,*,RP) becomes True 2213 The downstream state for (*,*,RP) has changed so that at least 2214 one interface is in immediate_olist(*,*,RP), making 2215 JoinDesired(*,*,RP) become True. 2217 The upstream (*,*,RP) state machine transitions to Joined 2218 state. Send Join(*,*,RP) to the appropriate upstream 2219 neighbor, which is MRIB.next_hop(RP). Set the Join Timer (JT) 2220 to expire after t_periodic seconds. 2222 Transitions from Joined State 2224 When the upstream (*,*,RP) state-machine is in Joined state, the 2225 following events may trigger state transitions: 2227 JoinDesired(*,*,RP) becomes False 2228 The downstream state for (*,*,RP) has changed so no interface 2229 is in immediate_olist(*,*,RP), making JoinDesired(*,*,RP) 2230 become False. 2232 The upstream (*,*,RP) state machine transitions to NotJoined 2233 state. Send Prune(*,*,RP) to the appropriate upstream 2234 neighbor, which is MRIB.next_hop(RP). Cancel the Join Timer 2235 (JT). 2237 Join Timer Expires 2238 The Join Timer (JT) expires, indicating time to send a 2239 Join(*,*,RP) 2240 Send Join(*,*,RP) to the appropriate upstream neighbor, which 2241 is MRIB.next_hop(RP). Restart the Join Timer (JT) to expire 2242 after t_periodic seconds. 2244 See Join(*,*,RP) to MRIB.next_hop(RP) 2245 This event is only relevant if RPF_interface(RP) is a shared 2246 medium. This router sees another router on RPF_interface(RP) 2247 send a Join(*,*,RP) to MRIB.next_hop(RP). This causes this 2248 router to suppress its own Join. 2250 The upstream (*,*,RP) state machine remains in Joined state. 2251 If the Join Timer is set to expire in less than t_suppressed 2252 seconds, reset it so that it expires after t_suppressed 2253 seconds. If the Join Timer is set to expire in more than 2254 t_suppressed seconds, leave it unchanged. 2256 See Prune(*,*,RP) to MRIB.next_hop(RP) 2257 This event is only relevant if RPF_interface(RP) is a shared 2258 medium. This router sees another router on RPF_interface(RP) 2259 send a Prune(*,*,RP) to MRIB.next_hop(RP). As this router is 2260 in Joined state, it must override the Prune after a short 2261 random interval. 2263 The upstream (*,*,RP) state machine remains in Joined state. 2264 If the Join Timer is set to expire in more than t_override 2265 seconds, reset it so that it expires after t_override seconds. 2266 If the Join Timer is set to expire in less than t_override 2267 seconds, leave it unchanged. 2269 Topology Change wrt MRIB.next_hop(RP) 2270 A route changed in the routing base stored in the MRIB so that 2271 the next hop towards the RP is a different neighbor from 2272 before. 2274 The upstream (*,*,RP) state machine remains in Joined state. 2275 Send Prune(*,*,RP) to the old upstream neighbor, which is the 2276 old value of MRIB.next_hop(RP). Send Join(*,*,RP) to the new 2277 upstream neighbor which is the new value of MRIB.next_hop(RP). 2278 Set the Join Timer (JT) to expire after t_periodic seconds. 2280 MRIB.next_hop(RP) GenID changes 2281 The Generation ID of the router that is MRIB.next_hop(RP) 2282 changes. This normally means that this neighbor has lost 2283 state, and so the state must be refreshed. 2285 The upstream (*,*,RP) state machine remains in Joined state. 2286 If the Join Timer is set to expire in more than t_override 2287 seconds, reset it so that it expires after t_override seconds. 2289 4.4.6. Sending (*,G) Join/Prune Messages 2291 The per-interface state-machines for (*,G) hold join state from 2292 downstream PIM routers. This state then determines whether a router 2293 needs to propagate a Join(*,G) upstream towards the RP. 2295 If a router wishes to propagate a Join(*,G) upstream, it must also watch 2296 for messages on its upstream interface from other routers on that 2297 subnet, and these may modify its behavior. If it sees a Join(*,G) to 2298 the correct upstream neighbor, it should suppress its own Join(*,G). If 2299 it sees a Prune(*,G) to the correct upstream neighbor, it should be 2300 prepared to override that prune by sending a Join(*,G) almost 2301 immediately. Finally, if it sees the Generation ID (see Section 4.6) of 2302 the correct upstream neighbor change, it knows that the upstream 2303 neighbor has lost state, and it should be prepared to refresh the state 2304 by sending a Join(*,G) almost immediately. 2306 In addition if the MRIB changes to indicate that the next hop towards 2307 the RP has changed, the router should prune off from the old next hop, 2308 and join towards the new next hop. 2310 The upstream (*,G) state-machine only contains two states: 2312 Not Joined 2313 The downstream state-machines indicate that the router does not 2314 need to join the RP tree for this group. 2316 Joined 2317 The downstream state-machines indicate that the router would like 2318 to join the RP tree for this group. 2320 In addition, one timer JT(*,G) is kept which is used to trigger the 2321 sending of a Join(*,G) to the upstream next hop towards the RP, 2322 RPF'(*,G). 2324 +-----------------------------------+ 2325 | Figures omitted from text version | 2326 +-----------------------------------+ 2328 Figure 7: Upstream (*,G) state-machine 2330 In tabular form, the state machine is: 2332 +---------------------+-------------------------------------------------+ 2333 | | Event | 2334 | Prev State +-------------------------+-----------------------+ 2335 | | JoinDesired(*,G) | JoinDesired(*,G) | 2336 | | ->True | ->False | 2337 +---------------------+-------------------------+-----------------------+ 2338 | | -> J state | - | 2339 | NotJoined (NJ) | Send Join(*,G); | | 2340 | | Set Timer to | | 2341 | | t_periodic | | 2342 +---------------------+-------------------------+-----------------------+ 2343 | Joined (J) | - | -> NJ state | 2344 | | | Send Prune(*,G) | 2345 +---------------------+-------------------------+-----------------------+ 2347 In addition, we have the following transitions which occur within the 2348 Joined state: 2350 +-----------------------------------------------------------------------+ 2351 | In Joined (J) State | 2352 +-----------------+-----------------+-----------------+-----------------+ 2353 |Timer Expires | See Join(*,G) | See Prune(*,G) | RPF'(*,G) | 2354 | | to RPF'(*,G) | to RPF'(*,G) | changes | 2355 +-----------------+-----------------+-----------------+-----------------+ 2356 |Send | Increase Timer | Decrease Timer | Decrease Timer | 2357 |Join(*,G); Set | to | to t_override | to t_override | 2358 |Timer to | t_suppressed | | | 2359 |t_periodic | | | | 2360 +-----------------+-----------------+-----------------+-----------------+ 2362 +-----------------------------------------------------------------------+ 2363 | In Joined (J) State | 2364 +----------------------------------+------------------------------------+ 2365 | topology change wrt | RPF'(*,G) GenID changes | 2366 | MRIB.next_hop(RP) | | 2367 +----------------------------------+------------------------------------+ 2368 | Send Join(*,G) to new | Decrease Timer to | 2369 | next hop; Send | t_override | 2370 | Prune(*,G) to old next | | 2371 | hop; set Timer to | | 2372 | t_periodic | | 2373 +----------------------------------+------------------------------------+ 2374 This state machine uses the following macro: 2376 bool JoinDesired(*,G) { 2377 if immediate_olist(*,G) != NULL 2378 return TRUE 2379 else 2380 return FALSE 2381 } 2383 JoinDesired(*,G) is true when the router has forwarding state that would 2384 cause it to forward traffic for G using shared tree state. Note that 2385 although JoinDesired is true, the router's sending of a Join(*,G) 2386 message may be suppressed by another router sending a Join(*,G) onto the 2387 upstream interface. 2389 Transitions from NotJoined State 2391 When the upstream (*,G) state-machine is in NotJoined state, the 2392 following event may trigger a state transition: 2394 JoinDesired(*,G) becomes True 2395 The downstream state for (*,G) has changed so that at least 2396 one interface is in immediate_olist(*,G), making 2397 JoinDesired(*,G) become True. 2399 The upstream (*,G) state machine transitions to Joined state. 2400 Send Join(*,G) to the appropriate upstream neighbor, which is 2401 RPF'(*,G). Set the Join Timer (JT) to expire after t_periodic 2402 seconds. 2404 Transitions from Joined State 2406 When the upstream (*,G) state-machine is in Joined state, the following 2407 events may trigger state transitions: 2409 JoinDesired(*,G) becomes False 2410 The downstream state for (*,G) has changed so no interface is 2411 in immediate_olist(*,G), making JoinDesired(*,G) become False. 2413 The upstream (*,G) state machine transitions to NotJoined 2414 state. Send Prune(*,G) to the appropriate upstream neighbor, 2415 which is RPF'(*,G). Cancel the Join Timer (JT). 2417 Join Timer Expires 2418 The Join Timer (JT) expires, indicating time to send a 2419 Join(*,G) 2420 Send Join(*,G) to the appropriate upstream neighbor, which is 2421 RPF'(*,G). Restart the Join Timer (JT) to expire after 2422 t_periodic seconds. 2424 See Join(*,G) to RPF'(*,G) 2425 This event is only relevant if RPF_interface(RP(G)) is a 2426 shared medium. This router sees another router on 2427 RPF_interface(RP(G)) send a Join(*,G) to RPF'(*,G). This 2428 causes this router to suppress its own Join. 2430 The upstream (*,G) state machine remains in Joined state. If 2431 the Join Timer is set to expire in less than t_suppressed 2432 seconds, reset it so that it expires after t_suppressed 2433 seconds. If the Join Timer is set to expire in more than 2434 t_suppressed seconds, leave it unchanged. 2436 See Prune(*,G) to RPF'(*,G) 2437 This event is only relevant if RPF_interface(RP(G)) is a 2438 shared medium. This router sees another router on 2439 RPF_interface(RP(G)) send a Prune(*,G) to RPF'(*,G). As this 2440 router is in Joined state, it must override the Prune after a 2441 short random interval. 2443 The upstream (*,G) state machine remains in Joined state. If 2444 the Join Timer is set to expire in more than t_override 2445 seconds, reset it so that it expires after t_override seconds. 2446 If the Join Timer is set to expire in less than t_override 2447 seconds, leave it unchanged. 2449 RPF'(*,G) changes 2450 The current net hop towards the RP changes due an Assert(*,G) 2451 on the RPF_interface(RP(G)). 2453 The upstream (*,G) state machine remains in Joined state. If 2454 the Join Timer is set to expire in more than t_override 2455 seconds, reset it so that it expires after t_override seconds. 2456 If the Join Timer is set to expire in less than t_override 2457 seconds, leave it unchanged. 2459 Topology Change wrt MRIB.next_hop(RP) 2460 A route changed in the routing base stored in the MRIB so that 2461 the next hop towards the RP is a different neighbor from 2462 before. 2464 The upstream (*,G) state machine remains in Joined state. 2465 Send Prune(*,G) to the old upstream neighbor, which is the old 2466 value of RPF'(*,G). Send Join(*,G) to the new upstream 2467 neighbor which is the new value of RPF(*,G). Note that the 2468 Join goes to RPF(*,G) and not RPF'(*,G) even if the new 2469 neighbor is on the same interface as the old one because the 2470 routing change may cause the assert state to be incorrect. Set 2471 the Join Timer (JT) to expire after t_periodic seconds. 2473 RPF'(*,G) GenID changes 2474 The Generation ID of the router that is RPF'(*,G) changes. 2475 This normally means that this neighbor has lost state, and so 2476 the state must be refreshed. 2478 The upstream (*,G) state machine remains in Joined state. If 2479 the Join Timer is set to expire in more than t_override 2480 seconds, reset it so that it expires after t_override seconds. 2482 4.4.7. Sending (S,G) Join/Prune Messages 2484 The per-interface state-machines for (S,G) hold join state from 2485 downstream PIM routers. This state then determines whether a router 2486 needs to propagate a Join(S,G) upstream towards the source. 2488 If a router wishes to propagate a Join(S,G) upstream, it must also watch 2489 for messages on its upstream interface from other routers on that 2490 subnet, and these may modify its behavior. If it sees a Join(S,G) to 2491 the correct upstream neighbor, it should suppress its own Join(S,G). If 2492 it sees a Prune(S,G), Prune(S,G,rpt), or Prune(*,G) to the correct 2493 upstream neighbor towards S, it should be prepared to override that 2494 prune by scheduling a Join(S,G) to be sent (almost) immediately. 2495 Finally, if it sees the Generation ID of its upstream neighbor change, 2496 it knows that the upstream neighbor has lost state, and it should 2497 refresh the state by scheduling a Join(S,G) to be sent (almost) 2498 immediately. 2500 In addition if MRIB changes cause the next hop towards the source to 2501 change, the router should send a prune to the old next hop, and a join 2502 to the new next hop. 2504 The upstream (S,G) state-machine only contains two states: 2506 Not Joined 2507 The downstream state machines and IGMP information do not indicate 2508 that the router needs to join the shortest-path tree for this 2509 (S,G). 2511 Joined 2512 The downstream state machines and IGMP information indicate that 2513 the router should join the shortest-path tree for this (S,G). 2515 In addition, one timer JT(S,G) is kept which is used to trigger the 2516 sending of a Join(S,G) to the upstream next hop toward S, RPF'(S,G). 2518 +-----------------------------------+ 2519 | Figures omitted from text version | 2520 +-----------------------------------+ 2522 Figure 8: Upstream (S,G) state-machine 2524 In tabular form, the state machine is: 2526 +--------------------++-------------------------------------------------+ 2527 | || Event | 2528 | Prev State ++-----------------------+-------------------------+ 2529 | || JoinDesired(S,G) | JoinDesired(S,G) | 2530 | || ->True | ->False | 2531 +--------------------++-----------------------+-------------------------+ 2532 | NotJoined (NJ) || -> J state | - | 2533 | || Send Join(S,G); | | 2534 | || Set Timer to | | 2535 | || t_periodic | | 2536 +--------------------++-----------------------+-------------------------+ 2537 | Joined (J) || - | -> NJ state | 2538 | || | Send Prune(S,G); | 2539 | || | Set SPTbit(S,G) to | 2540 | || | FALSE | 2541 +--------------------++-----------------------+-------------------------+ 2542 In addition, we have the following transitions which occur within the 2543 Joined state: 2545 +-----------------------------------------------------------------------+ 2546 | In Joined (J) State | 2547 +-----------------+-----------------+-----------------+-----------------+ 2548 |Timer Expires | See Join(S,G) | See Prune(S,G) | See Prune | 2549 | | to RPF'(S,G) | to RPF'(S,G) | (S,G,rpt) to | 2550 | | | | RPF'(S,G) | 2551 +-----------------+-----------------+-----------------+-----------------+ 2552 |Send | Increase Timer | Decrease Timer | Decrease Timer | 2553 |Join(S,G); Set | to t_suppr | to t_override | to t_override | 2554 |Timer to | | | | 2555 |t_periodic | | | | 2556 +-----------------+-----------------+-----------------+-----------------+ 2558 +-----------------------------------------------------------------------+ 2559 | In Joined (J) State | 2560 +----------------------+-------------------------+----------------------+ 2561 | See Prune(*,G) to | topology change | RPF'(S,G) GenID | 2562 | RPF'(S,G) | wrt | changes | 2563 | | MRIB.next_hop(S) | | 2564 +----------------------+-------------------------+----------------------+ 2565 | Decrease Timer to | Send Join(S,G) to | Decrease Timer to | 2566 | t_override | new next hop; Send | t_override | 2567 | | Prune(S,G) to old | | 2568 | | next hop; Set | | 2569 | | Timer to | | 2570 | | t_periodic | | 2571 +----------------------+-------------------------+----------------------+ 2573 This state machine uses the following macro: 2575 bool JoinDesired(S,G) { 2576 return( immediate_olist(S,G) != NULL 2577 OR ( KeepaliveTimer(S,G) is running 2578 AND inherited_olist(S,G) != NULL ) ) 2579 } 2581 JoinDesired(S,G) is true when the router has forwarding state that would 2582 cause it to forward traffic for G using source tree state. The source 2583 tree state can either be as a result of active source-specific join 2584 state, or the (S,G) keepalive timer and active non-source-specific 2585 state. Note that although JoinDesired is true, the router's sending of a 2586 Join(S,G) message may be suppressed by another router sending a 2587 Join(S,G) onto the upstream interface. 2589 Transitions from NotJoined State 2591 When the upstream (S,G) state-machine is in NotJoined state, the 2592 following event may trigger a state transition: 2594 JoinDesired(S,G) becomes True 2595 The downstream state for (S,G) has changed so that at least 2596 one interface is in inherited_olist(S,G), making 2597 JoinDesired(S,G) become True. 2599 The upstream (S,G) state machine transitions to Joined state. 2600 Send Join(S,G) to the appropriate upstream neighbor, which is 2601 RPF'(S,G). Set the Join Timer (JT) to expire after t_periodic 2602 seconds. 2604 Transitions from Joined State 2606 When the upstream (S,G) state-machine is in Joined state, the following 2607 events may trigger state transitions: 2609 JoinDesired(S,G) becomes False 2610 The downstream state for (S,G) has changed so no interface is 2611 in inherited_olist(S,G), making JoinDesired(S,G) become False. 2613 The upstream (S,G) state machine transitions to NotJoined 2614 state. Send Prune(S,G) to the appropriate upstream neighbor, 2615 which is RPF'(S,G). Cancel the Join Timer (JT). 2617 Join Timer Expires 2618 The Join Timer (JT) expires, indicating time to send a 2619 Join(S,G) 2621 Send Join(S,G) to the appropriate upstream neighbor, which is 2622 RPF'(S,G). Restart the Join Timer (JT) to expire after 2623 t_periodic seconds. 2625 See Join(S,G) to RPF'(S,G) 2626 This event is only relevant if RPF_interface(S) is a shared 2627 medium. This router sees another router on RPF_interface(S) 2628 send a Join(S,G) to RPF'(S,G). This causes this router to 2629 suppress its own Join. 2631 The upstream (S,G) state machine remains in Joined state. If 2632 the Join Timer is set to expire in less than t_suppressed 2633 seconds, reset it so that it expires after t_suppressed 2634 seconds. If the Join Timer is set to expire in more than 2635 t_suppressed seconds, leave it unchanged. 2637 See Prune(S,G) to RPF'(S,G) 2638 This event is only relevant if RPF_interface(S) is a shared 2639 medium. This router sees another router on RPF_interface(S) 2640 send a Prune(S,G) to RPF'(S,G). As this router is in Joined 2641 state, it must override the Prune after a short random 2642 interval. 2644 The upstream (S,G) state machine remains in Joined state. If 2645 the Join Timer is set to expire in more than t_override 2646 seconds, reset it so that it expires after t_override seconds. 2648 See Prune(S,G,rpt) to RPF'(S,G) 2649 This event is only relevant if RPF_interface(S) is a shared 2650 medium. This router sees another router on RPF_interface(S) 2651 send a Prune(S,G,rpt) to RPF'(S,G). If the upstream router is 2652 an RFC 2362 compliant PIM router, then the Prune(S,G,rpt) will 2653 cause it to stop forwarding. For backwards compatibility, 2654 this router should override the prune so that forwarding 2655 continues. 2657 The upstream (S,G) state machine remains in Joined state. If 2658 the Join Timer is set to expire in more than t_override 2659 seconds, reset it so that it expires after t_override seconds. 2661 See Prune(*,G) to RPF'(S,G) 2662 This event is only relevant if RPF_interface(S) is a shared 2663 medium. This router sees another router on RPF_interface(S) 2664 send a Prune(*,G) to RPF'(S,G). If the upstream router is an 2665 RFC 2362 compliant PIM router, then the Prune(*,G) will cause 2666 it to stop forwarding. For backwards compatibility, this 2667 router should override the prune so that forwarding continues. 2669 The upstream (S,G) state machine remains in Joined state. If 2670 the Join Timer is set to expire in more than t_override 2671 seconds, reset it so that it expires after t_override seconds. 2673 RPF'(S,G) changes 2674 The current net hop towards the RP changes due an Assert(S,G) 2675 on the RPF_interface(S). 2677 The upstream (S,G) state machine remains in Joined state. If 2678 the Join Timer is set to expire in more than t_override 2679 seconds, reset it so that it expires after t_override seconds. 2680 If the Join Timer is set to expire in less than t_override 2681 seconds, leave it unchanged. 2683 Topology Change wrt MRIB.next_hop(S) 2684 A route changed in the routing base stored in the MRIB so that 2685 the next hop towards S is a different neighbor from before. 2687 The upstream (S,G) state machine remains in Joined state. 2688 Send Prune(S,G) to the old upstream neighbor, which is the old 2689 value of RPF'(S,G). Send Join(S,G) to the new upstream 2690 neighbor which is the new value of RPF(S,G). Note that the 2691 Join goes to RPF(S,G) and not RPF'(S,G) even if the new 2692 neighbor is on the same interface as the old one because the 2693 routing change may cause the assert state to be incorrect. Set 2694 the Join Timer (JT) to expire after t_periodic seconds. 2696 RPF'(S,G) GenID changes 2697 The Generation ID of the router that is RPF'(S,G) changes. 2698 This normally means that this neighbor has lost state, and so 2699 the state must be refreshed. 2701 The upstream (S,G) state machine remains in Joined state. If 2702 the Join Timer is set to expire in more than t_override 2703 seconds, reset it so that it expires after t_override seconds. 2705 4.4.8. (S,G,rpt) Periodic Messages 2707 (S,G,rpt) Joins and Prunes are (S,G) Joins or Prunes sent on the RP tree 2708 with the RPT bit set, either to modify the results of (*,G) Joins, or to 2709 override the behavior of other upstream LAN peers. The next section 2710 describes the rules for sending triggered messages. This section 2711 describes the rules for including an Prune(S,G,rpt) message with a 2712 Join(*,G). 2714 When a router is going to send a Join(*,G), it should use the following 2715 pseudocode, for each (S,G) for which it has state, to decide whether to 2716 include a Prune(S,G,rpt) in the compound Join/Prune message: 2718 if( SPTbit(S,G) == TRUE ) { 2719 # Note: If receiving (S,G) on the SPT, we only prune off the 2720 # shared tree if the rpf neighbors differ. 2721 if( RPF'(*,G) != RPF'(S,G) ) { 2722 add Prune(S,G,rpt) to compound message 2723 } 2724 } else if ( inherited_olist(S,G,rpt) == NULL ) { 2725 # Note: all (*,G) olist interfaces sent rpt prunes for (S,G). 2726 add Prune(S,G,rpt) to compound message 2727 } else if ( RPF'(*,G) != RPF'(S,G,rpt) { 2728 # Note: we joined the shared tree, but there was an (S,G) assert and 2729 # the source tree RPF neighbor is different. 2730 add Prune(S,G,rpt) to compound message 2731 } 2733 Note that Join(S,G,rpt) is not normally sent as a periodic message, but 2734 only as a triggered message. 2736 4.4.9. State Machine for (S,G,rpt) Triggered Messages 2738 The state machine for (S,G,rpt) triggered messages is required per-(S,G) 2739 when there is (*,G) or (*,*,RP) join state at a router, and the router 2740 or any of its upstream LAN peers wishes to prune S off the RP tree. 2742 There are three states in the state-machine. One of the states is when 2743 there is neither (*,G) nor (*,*,RP(G)) join state at this router. If 2744 there is (*,G) or (*,*,RP(G)) join state at the router, then the state 2745 machine must be at one of the other two states: 2747 Pruned(S,G,rpt) 2748 (*,G) or (*,*,RP(G)) Joined, but (S,G,rpt) pruned 2750 NotPruned(S,G,rpt) 2751 (*,G) or (*,*,RP(G)) Joined, and (S,G,rpt) not pruned 2753 RPTNotJoined(G) 2754 neither (*,G) nor (*,*,RP(G)) has not been joined. 2756 In addition there is an (S,G,rpt) Override Timer, OT(S,G,rpt), which is 2757 used to delay triggered Join(S,G,rpt) messages to prevent implosions of 2758 triggered messages. 2760 +-----------------------------------+ 2761 | Figures omitted from text version | 2762 +-----------------------------------+ 2764 Figure 9: Upstream (S,G,rpt) state-machine for triggered messages 2766 In tabular form, the state machine is: 2768 +-------------++---------------------------------------------------------------+ 2769 | || Event | 2770 | ++-------------+-------------+------------------+----------------+ 2771 |Prev State |PruneDesired |PruneDesired |RPTJoinDesired(G) |inherited_olist | 2772 | |(S,G,rpt) |(S,G,rpt) |->False |(S,G,rpt) | 2773 | |->True |->False | |->non-NULL | 2774 +-------------++-------------+-------------+------------------+----------------+ 2775 |RPTNotJoined |+> P state |- |- |-> NP state | 2776 |(G) (NJ) || | | | | 2777 +-------------++-------------+-------------+------------------+----------------+ 2778 |Pruned |+ |-> NP state |-> NJ state |- | 2779 |(S,G,rpt) (P)|| |Send Join | | | 2780 | || |(S,G,rpt) | | | 2781 +-------------++-------------+-------------+------------------+----------------+ 2782 |NotPruned |+> P state |- |-> NJ state |- | 2783 |(S,G,rpt) |Send Prune | | | | 2784 |(NP) |(S,G,rpt); | | | | 2785 | |Stop OT timer | | | | 2786 +-------------++-------------+-------------+------------------+----------------+ 2787 Additionally, we have the following transitions within the 2788 NotPruned(S,G,rpt) state which are all used for prune override behavior. 2790 +-----------------------------------------------------------------------+ 2791 | In NotPruned(S,G,rpt) State | 2792 +------------+--------------+---------------+------------+--------------+ 2793 |OT timer |See Prune | See Join |See Prune | RPF' | 2794 |expires |(S,G,rpt) to | (S,G,rpt) to |(S,G) to | (S,G,rpt) -> | 2795 | |RPF' | RPF' |RPF' | RPF' (*,G) | 2796 | |(S,G,rpt) | (S,G,rpt) |(S,G,rpt) | | 2797 +------------+--------------+---------------+------------+--------------+ 2798 |Send Join |OT timer = | stop OT |OT timer = | OT timer = | 2799 |(S,G,rpt); |min(timer, | timer |min(timer, | min(timer, | 2800 |Stop OT |t_po) | |t_po) | t_po) | 2801 |timer | | | | | 2802 +------------+--------------+---------------+------------+--------------+ 2804 Note that the min function in the above state machine considers a non- 2805 running timer to have an infinite value (e.g. min(not-running, t_po) = 2806 t_po). 2808 This state machine uses the following macros: 2810 bool RPTJoinDesired(G) { 2811 return (JoinDesired(*,G) || JoinDesired(*,*,RP(G))) 2812 } 2814 RPTJoinDesired(G) is true when the router has forwarding state that 2815 would cause it to forward traffic for G using either (*,G) or (*,*,RP) 2816 shared tree state. 2818 bool PruneDesired(S,G,rpt) { 2819 return ( RPTJoinDesired(G) AND 2820 ( inherited_olist(S,G,rpt) == NULL 2821 OR (SPTbit(S,G)==TRUE 2822 AND (RPF'(*,G) != RPF'(S,G)) ))) 2823 } 2825 PruneDesired(S,G,rpt) can only be true if RPTJoinDesired(G) is true. If 2826 RPTJoinDesired(G) is true, then PruneDesired(S,G,rpt) is true if either 2827 there are no outgoing interfaces that S would be forwarded on, or if the 2828 router has active (S,G) forwarding state but RPF'(*,G) != RPF'(S,G). 2830 The state machine contains the following transition events: 2832 See Join(S,G,rpt) to RPF'(S,G,rpt) 2833 This event is only relevant in the "Not Pruned" state. 2835 The router sees a Join(S,G,rpt) from someone else to RPF'(S,G,rpt), 2836 which is the correct upstream neighbor. If we're in "NotPruned" 2837 state and the (S,G,rpt) override timer is running, then this is 2838 because we have been triggered to send our own Join(S,G,rpt) to 2839 RPF'(S,G,rpt). Someone else beat us to it, so there's no need to 2840 send our own Join. 2842 The action is to cancel the override timer. 2844 See Prune(S,G,rpt) to RPF'(S,G,rpt) 2845 This event is only relevant in the "NotPruned" state. 2847 The router sees a Prune(S,G,rpt) from someone else to to 2848 RPF'(S,G,rpt), which is the correct upstream neighbor. If we're in 2849 the "NotPruned" state, then we want to continue to receive traffic 2850 from S destined for G, and that traffic is being supplied by 2851 RPF'(S,G,rpt). Thus we need to override the Prune. 2853 The action is to set the (S,G,rpt) time to the randomized prune- 2854 override interval. However if the override timer is already 2855 running, we only set the timer if doing so would set it to a lower 2856 value. At the end of this interval, if no-one else has sent a 2857 Join, then we will do so. 2859 See Prune(S,G) to RPF'(S,G,rpt) 2860 This event is only relevant in the "NotPruned" state. 2862 This transition and action are the same as the above transition and 2863 action, except that the Prune does not have the RPT bit set. This 2864 transition is necessary to be compatible with existing routers that 2865 don't maintain separate (S,G) and (S,G,rpt) state. 2867 The (S,G,rpt) prune override timer expires 2868 This event is only relevant in the "NotPruned" state. 2870 When the override timer expires, we must send a Join(S,G,rpt) to 2871 RPF'(S,G,rpt) to override the Prune message that caused the timer 2872 to be running. We only send this if RPF'(S,G,rpt) equals RPF'(*,G) 2873 - if this were not the case, then the Join might be sent to a 2874 router that does not have (*,G) or (*,*,RP(G)) Join state, and so 2875 the behavior would not be well defined. If RPF'(S,G,rpt) is not 2876 the same as RPF'(*,G), then it may stop forwarding S. However, if 2877 this happens, then the router will send an AssertCancel(S,G), which 2878 would then cause RPF'(S,G,rpt) to become equal to RPF'(*,G) (see 2879 below). 2881 RPF'(S,G,rpt) changes to become equal to RPF'(*,G) 2882 This event is only relevant in the "NotPruned" state. 2884 RPF'(S,G,rpt) can only be different from RPF'(*,G) if an (S,G) 2885 Assert has happened, which means that traffic from S is arriving on 2886 the SPT, and so Prune(S,G,rpt) will have been sent to RPF'(*,G). 2887 When RPF'(S,G,rpt) changes to become equal to RPF'(*,G), we need to 2888 trigger a Join(S,G,rpt) to RPF'(*,G) to cause that router to start 2889 forwarding S again. 2891 The action is to set the (S,G,rpt) override timer to the randomized 2892 prune-override interval. However if the timer is already running, 2893 we only set the timer if doing so would set it to a lower value. 2894 At the end of this interval, if no-one else has sent a Join, then 2895 we will do so. 2897 PruneDesired(S,G,rpt)->TRUE 2898 See macro above. 2900 The router wishes to receive traffic for G, but does not wish to 2901 receive traffic from S destined for G. This causes the router to 2902 transition into the Pruned state. 2904 If the router was previously in NotPruned state, then the action is 2905 to send a Prune(S,G,rpt) to RPF'(S,G,rpt). If the router was 2906 previously in RPTNotJoined(G) state, then there is no need to 2907 trigger an action in this state machine because sending a 2908 Prune(S,G,rpt) is handled by the rules for sending the Join(*,G) or 2909 Join(*,*,RP). 2911 PruneDesired(S,G,rpt)->FALSE 2912 See macro above. This transition is only relevant in the "Pruned" 2913 state. 2915 If the router is in the Pruned(S,G,rpt) state, and 2916 PruneDesired(S,G,rpt) changes to FALSE, this could be because the 2917 router no longer has RPTJoinDesired(G) true, or it now wishes to 2918 receive traffic from S again. If it is the former, then this 2919 transition should not happen, but instead the 2920 "RPTJoinDesired(G)->FALSE" transition should happen. Thus this 2921 transition should be interpreted as "PruneDesired(S,G,rpt)->FALSE 2922 AND RPTJoinDesired(G)==TRUE" 2924 The action is to send a Join(S,G,rpt) to RPF'(S,G,rpt). 2926 RPTJoinDesired(G)->FALSE 2927 The router no longer wishes to receive any traffic destined for G 2928 on the RP Tree. This causes a transition to the RPTNotJoined(G) 2929 state. Any actions are handled by the appropriate upstream state 2930 machine for (*,G) or (*,*,RP). 2932 inherited_olist(S,G,rpt) becomes non-NULL 2933 This transition is only relevant in the RPTNotJoined(G) state. 2935 The router has joined the RP tree (handled by the (*,G) or (*,*,RP) 2936 upstream state machine as appropriate), and wants to receive 2937 traffic from S. This does not trigger any events in this state 2938 machine, but causes a transition to the NotPruned(S,G,rpt) state. 2940 4.5. PIM Assert Messages 2942 4.5.1. (S,G) Assert Message State Machine 2944 The (S,G) Assert state machine for interface I is shown in Figure 10. 2945 There are three states: 2947 NoInfo (NI) 2948 This router has no (S,G) assert state on interface I. 2950 I am Assert Winner (W) 2951 This router has won an (S,G) assert on interface I. It is now 2952 responsible for forwarding traffic from S destined for G out of 2953 interface I. Irrespective of whether it is the DR for I, while a 2954 router is the assert winner, it is also responsible for forwarding 2955 traffic onto I on behalf of local hosts on I that have made 2956 membership requests that specifically refer to S (and G). 2958 I am Assert Loser (L) 2959 This router has lost an (S,G) assert on interface I. It must not 2960 forward packets from S destined for G onto interface I. If it is 2961 the DR on I, it is no longer responsible for forwarding traffic 2962 onto I to satisfy local hosts with membership requests that 2963 specifically refer to S and G. 2965 In addition there is also a assert timer (AT) that is used to time out 2966 asserts on the assert losers and to resend asserts on the assert winner. 2968 +-----------------------------------+ 2969 | Figures omitted from text version | 2970 +-----------------------------------+ 2972 Figure 10: Per-interface (S,G) Assert State-machine 2974 In tabular form the state machine is: 2976 +-----------------------------------------------------------------------+ 2977 | In NoInfo (NI) State | 2978 +---------------+-------------------+------------------+----------------+ 2979 | Receive | Receive Assert | Data arrives | Receive | 2980 | Inferior | with RPTbit | from S to G on | Preferred | 2981 | Assert with | set and | I and | Assert with | 2982 | RPTbit clear | CouldAssert | CouldAssert | RPTbit clear | 2983 | and | (S,G,I) | (S,G,I) | and AssTrDes | 2984 | CouldAssert | | | (S,G,I) | 2985 | (S,G,I) | | | | 2986 +---------------+-------------------+------------------+----------------+ 2987 | -> W state | -> W state | -> W state | -> L state | 2988 | [Actions A1] | [Actions A1] | [Actions A1] | [Actions A6] | 2989 +---------------+-------------------+------------------+----------------+ 2991 +-----------------------------------------------------------------------+ 2992 | In I Am Assert Winner (W) State | 2993 +-----------------+-----------------+------------------+----------------+ 2994 | Timer Expires | Receive | Receive | CouldAssert | 2995 | | Inferior | Preferred | (S,G,I) -> | 2996 | | Assert | Assert | FALSE | 2997 +-----------------+-----------------+------------------+----------------+ 2998 | -> W state | -> W state | -> L state | -> NI state | 2999 | [Actions A3] | [Actions A3] | [Actions A2] | [Actions A4] | 3000 +-----------------+-----------------+------------------+----------------+ 3002 +-----------------------------------------------------------------------+ 3003 | In I Am Assert Loser (L) State | 3004 +---------------+-------------------+-----------------+-----------------+ 3005 | Receive | Receive | Timer Expires | AssTrDes | 3006 | Preferred | Inferior | | (S,G,I) -> | 3007 | Assert | Assert from | | FALSE | 3008 | | Current Winner | | | 3009 +---------------+-------------------+-----------------+-----------------+ 3010 | -> L state | -> NI state | -> NI state | -> NI state | 3011 | [Actions A2] | [Actions A5] | [Actions A5] | [Actions A5] | 3012 +---------------+-------------------+-----------------+-----------------+ 3013 +-----------------------------------------------------------------------+ 3014 | In I Am Assert Loser (L) State | 3015 +----------------+-----------------+-----------------+------------------+ 3016 | my_metric -> | RPF interface | Receive | Receive Assert | 3017 | better than | stops being I | Join(S,G) on | from Current | 3018 | winner's | | interface I | Winner | 3019 | metric | | | | 3020 +----------------+-----------------+-----------------+------------------+ 3021 | -> NI state | -> NI state | -> NI State | -> L state | 3022 | [Actions A5] | [Actions A5] | [Actions A5] | [Actions A2] | 3023 +----------------+-----------------+-----------------+------------------+ 3025 Note that for reasons of compactness, "AssTrDes(S,G,I)" is used in the 3026 state-machine table to refer to AssertTrackingDesired(S,G,I). 3028 Terminology: 3029 A "preferred assert" is one with a better metric than the current 3030 winner. 3032 An "inferior assert" is one with a worse metric than 3033 my_assert_metric(S,G,I). 3034 The state machine uses the following macros: 3036 CouldAssert(S,G,I) = 3037 SPTbit(S,G)==TRUE 3038 AND (RPF_interface(S) != I) 3039 AND (I in ( ( joins(*,G) (-) prunes(S,G,rpt) ) 3040 (+) ( pim_include(*,G) (-) pim_exclude(S,G) ) 3041 (-) lost_assert(*,G) 3042 (+) joins(S,G) (+) pim_include(S,G) ) ) 3044 CouldAssert(S,G,I) is true for downstream interfaces which would be in 3045 the inherited_olist(S,G) if (S,G) assert information was not taken into 3046 account. 3048 AssertTrackingDesired(S,G,I) = 3049 (I in ( ( joins(*,G) (-) prunes(S,G,rpt) ) 3050 (+) ( pim_include(*,G) (-) pim_exclude(S,G) ) 3051 (-) lost_assert(*,G) 3052 (+) joins(S,G) (+) pim_include(S,G) ) ) 3053 OR (RPF_interface(S)==I AND JoinDesired(S,G)==TRUE) 3054 OR (RPF_interface(RP)==I AND JoinDesired(*,G)==TRUE 3055 AND SPTbit(S,G)==FALSE) 3057 AssertTrackingDesired(S,G,I) is true on any interface in which an (S,G) 3058 assert might affect our behavior. 3060 The first three lines of AssertTrackingDesired account for (*,G) join 3061 information received on I that might cause the router to be interested 3062 in asserts on I. 3064 The 4th line accounts for (S,G) join information received on I that 3065 might cause the router to be interested in asserts on I. 3067 The last three lines account for the fact that a router must keep track 3068 of assert information on upstream interfaces in order to send joins and 3069 prunes to the proper neighbor. 3071 Transitions from NoInfo State 3073 When in NoInfo state, the following events may trigger transitions: 3075 Receive Inferior Assert with RPTbit cleared 3076 An assert is received for (S,G) with the RPT bit cleared that 3077 is inferior to our own assert metric. The RPT bit cleared 3078 indicates that the sender of the assert had (S,G) forwarding 3079 state on this interface. If the assert is inferior to our 3080 metric, then we must also have (S,G) forwarding state as (S,G) 3081 asserts beat (*,G) asserts, and so we should be the assert 3082 winner. We transition to the "I am Assert Winner" state, and 3083 perform Actions A1 (below). 3085 Receive Assert with RPTbit set AND CouldAssert(S,G,I)==TRUE 3086 An assert is received for (S,G) on I with the RPT bit set 3087 (it's a (*,G) assert). CouldAssert(S,G,I) is TRUE only if we 3088 have (S,G) forwarding state on this interface, so we should be 3089 the assert winner. We transition to the "I am Assert Winner" 3090 state, and perform Actions A1 (below). 3092 An (S,G) data packet arrives on interface I, AND 3093 CouldAssert(S,G,I)==TRUE 3094 An (S,G) data packet arrived on an downstream interface which 3095 is in our (S,G) outgoing interface list. We optimistically 3096 assume that we will be the assert winner for this (S,G), and 3097 so we transition to the "I am Assert Winner" state, and 3098 perform Actions A1 (below) which will initiate the assert 3099 negotiation for (S,G). 3101 Receive Preferred Assert with RPT bit clear AND 3102 AssertTrackingDesired(S,G,I)==TRUE 3103 We're interested in (S,G) Asserts, either because I is a 3104 downstream interface for which we have (S,G) or (*,G) 3105 forwarding state, or because I is the upstream interface for S 3106 and we have (S,G) forwarding state. The received assert that 3107 has a better metric than our own, so we do not win the Assert. 3109 We transition to "I am Assert Loser" and perform actions A2 3110 (below). 3112 Transitions from Winner State 3114 When in "I am Assert Winner" state, the following events trigger 3115 transitions: 3117 Timer Expires 3118 The (S,G) assert timer expires. As we're in the Winner state, 3119 then we must still have (S,G) forwarding state that is 3120 actively being kept alive. We re-send the (S,G) Assert and 3121 restart the timer (Action A3 below). Note that the assert 3122 winner's timer is engineered to expire shortly before timers 3123 on assert losers; this prevents unnecessary thrashing of the 3124 forwarder and periodic flooding of duplicate packets. 3126 Receive Inferior Assert 3127 We receive an (S,G) assert or (*,G) assert mentioning S that 3128 has a worse metric than our own. Whoever sent the assert is 3129 in error, and so we re-send an (S,G) Assert, and restart the 3130 timer (Action A3 below). 3132 Receive Preferred Assert 3133 We receive an (S,G) assert that has a better metric than our 3134 own. We transition to "I am Assert Loser" state and perform 3135 actions A2 (below). Note that this may affect the value of 3136 JoinDesired(S,G) which could cause transitions in the upstream 3137 (S,G) state machine. 3139 CouldAssert(S,G,I) -> FALSE 3140 Our (S,G) forwarding state or RPF interface changed so as to 3141 make CouldAssert(S,G,I) become false. We can no longer 3142 perform the actions of the assert winner, and so we transition 3143 to NoInfo state and perform actions A4 (below). This includes 3144 sending a "cancelling assert" with an infinite metric. 3146 Transitions from Loser State 3148 When in "I am Assert Loser" state, the following transitions can occur: 3150 Receive Preferred Assert 3151 We receive an assert that is better than that of the current 3152 assert winner. We stay in Loser state, and perform actions A2 3153 below. 3155 Receive Inferior Assert from Current Winner 3156 We receive an assert from the current assert winner that is 3157 worse than our own metric for this group (typically the 3158 winner's metric became worse). We transition to NoInfo state, 3159 deleting the (S,G) assert information and allowing the normal 3160 PIM Join/Prune mechanisms to operate. Usually we will 3161 eventually re-assert and win when data packets from S have 3162 started flowing again. 3164 Timer Expires 3165 The (S,G) assert timer expires. We transition to NoInfo 3166 state, deleting the (S,G) assert information. 3168 AssertTrackingDesired(S,G,I)->FALSE 3169 AssertTrackingDesired(S,G,I) becomes FALSE. Our forwarding 3170 state has changed so that (S,G) Asserts on interface I are no 3171 longer of interest to us. We transition to the NoInfo state, 3172 deleting the (S,G) assert information. 3174 My metric becomes better than the assert winner's metric 3175 my_assert_metric(S,G,I) has changed so that now my assert | 3176 metric for (S,G) is better than the metric we have stored for | 3177 current assert winner. This might happen the underlying | 3178 routing metric changes, or when when CouldAssert(S,G,I) | 3179 becomes true; for example, when SPTbit(S,G) becomes true. We | 3180 transition to NoInfo state, delete this (S,G) assert state, | 3181 and allow the normal PIM Join/Prune mechanisms to operate. | 3182 Usually we will eventually re-assert and win when data packets | 3183 from S have started flowing again. | 3185 RPF interface changed away from interface I 3186 Interface I used to be the RPF interface for S, and now it is 3187 not. We transition to NoInfo state, delete this (S,G) assert 3188 state. 3190 Receive Join(S,G) 3191 We receive a Join(S,G) directed to my IP address in interface 3192 I. The action is to transition to NoInfo state, and delete 3193 this (S,G) assert state, and allow the normal PIM Join/Prune 3194 mechanisms to operate. If whoever sent the Join was in error, 3195 then the normal assert mechanism will eventually re-apply and 3196 we will lose the assert again. However whoever sent the 3197 assert may know that the previous assert winner has died, and 3198 so we may end up being the new forwarder. 3200 (S,G) Assert State-machine Actions 3202 A1: Send Assert(S,G) 3203 Set timer to (Assert_Time - Assert_Override_Interval) 3204 Store self as AssertWinner 3206 A2: Store new assert winner 3207 Set timer to Assert_Time 3209 A3: Send Assert(S,G) 3210 Set timer to (Assert_Time - Assert_Override_Interval) 3212 A4: Send AssertCancel(S,G) 3213 Delete assert info 3215 A5: Delete assert info 3217 A6: Store new assert winner 3218 Set timer to Assert_Time 3219 If I is RPF_interface(S) Set SPTbit(S,G) to TRUE. 3221 4.5.2. (*,G) Assert Message State Machine 3223 The (*,G) Assert state-machine for interface I is shown in Figure 11. 3224 There are three states: 3226 NoInfo (NI) 3227 This router has no (*,G) assert state on interface I. 3229 I am Assert Winner (W) 3230 This router has won an (*,G) assert on interface I. It is now 3231 responsible for forwarding traffic destined for G onto interface I 3232 with the exception of traffic for which it has (S,G) "I am Assert 3233 Loser" state. Irrespective of whether it is the DR for I, it is 3234 also responsible for handling the membership requests for G from 3235 local hosts on I. 3237 I am Assert Loser (L) 3238 This router has lost an (*,G) assert on interface I. It must not 3239 forward packets for G onto interface I with the exception of 3240 traffic from sources for which is has (S,G) "I am Assert Winner" 3241 state. If it is the DR, it is no longer responsible for handling 3242 the membership requests for group G from local hosts on I. 3244 In addition there is also an assert timer (AT) that is used to time out 3245 asserts on the assert losers and to resend asserts on the assert winner. 3247 It is important to note that no transition occurs in the (*,G) state 3248 machine as a result of receiving an assert message if the (S,G) assert 3249 state machine for the relevant S and G is not in the "NoInfo" state. 3251 +-----------------------------------+ 3252 | Figures omitted from text version | 3253 +-----------------------------------+ 3255 Figure 11: (*,G) Assert State-machine 3257 In tabular form the state machine is: 3259 +-----------------------------------------------------------------------+ 3260 | In NoInfo (NI) State | 3261 +-----------------------+-----------------------+-----------------------+ 3262 | Receive Inferior | Data arrives for G | Receive Preferred | 3263 | Assert with RPTbit | and CouldAssert | Assert with RPTbit | 3264 | set | (*,G,I) | set and AssTrDes | 3265 | | | (*,G,I) | 3266 +-----------------------+-----------------------+-----------------------+ 3267 | -> Winner state | -> Winner state | -> Loser state | 3268 | [Actions A1] | [Actions A1] | [Actions A2] | 3269 +-----------------------+-----------------------+-----------------------+ 3271 +-----------------------------------------------------------------------+ 3272 | In I Am Assert Winner (W) State | 3273 +-----------------+-----------------+------------------+----------------+ 3274 | Timer Expires | Receive | Receive | CouldAssert | 3275 | | Inferior | Preferred | (*,G,I) -> | 3276 | | Assert | Assert | FALSE | 3277 +-----------------+-----------------+------------------+----------------+ 3278 | -> W state | -> W state | -> L state | -> NI state | 3279 | [Actions A3] | [Actions A3] | [Actions A2] | [Actions A4] | 3280 +-----------------+-----------------+------------------+----------------+ 3282 +-----------------------------------------------------------------------+ 3283 | In I Am Assert Loser (L) State | 3284 +---------------+-------------------+-----------------+-----------------+ 3285 | Receive | Receive | Timer Expires | AssTrDes | 3286 | Preferred | Inferior | | (*,G,I) -> | 3287 | Assert | Assert from | | FALSE | 3288 | | Current Winner | | | 3289 +---------------+-------------------+-----------------+-----------------+ 3290 | -> L state | -> NI state | -> NI state | -> NI state | 3291 | [Actions A2] | [Actions A5] | [Actions A5] | [Actions A5] | 3292 +---------------+-------------------+-----------------+-----------------+ 3294 +-----------------------------------------------------------------------+ 3295 | In I Am Assert Loser (L) State | 3296 +----------------------+----------------------+-------------------------+ 3297 | my_metric -> | RPF interface | Receive Join(*,G) | 3298 | better than | stops being I | or Join(*,*,RP(G)) | 3299 | Winner's metric | | on Interface I | 3300 +----------------------+----------------------+-------------------------+ 3301 | -> NI state | -> NI state | -> NI State | 3302 | [Actions A5] | [Actions A5] | [Actions A5] | 3303 +----------------------+----------------------+-------------------------+ 3304 The state machine uses the following macros: 3306 CouldAssert(*,G,I) = 3307 ( I in ( joins(*,G) (+) joins(*,*,RP(G)) 3308 (+) pim_include(*,G)) ) 3309 AND RPF_interface(RP(G)) != I 3311 CouldAssert(*,G,I) is true on downstream interfaces for which we have 3312 (*,G) or (*,*,RP(G) join state, or local members that requested any 3313 traffic destined for G. 3315 AssertTrackingDesired(*,G,I) = 3316 CouldAssert(*,G) OR 3317 ( RPF_interface(RP(G)) == I AND RPTJoinDesired(G) ) 3319 AssertTrackingDesired(*,G,I) is true on any interface on which an (*,G) 3320 assert might affect our behavior. 3322 Note that for reasons of compactness, "AssTrDes(*,G,I)" is used in the 3323 state-machine table to refer to AssertTrackingDesired(*,G,I). 3325 Terminology: 3326 A "preferred assert" is one with a better metric than the current 3327 winner. 3329 An "inferior assert" is one with a worse metric than 3330 my_assert_metric(S,G). 3332 Transitions from NoInfo State 3334 When in NoInfo state, the following events trigger transitions, but only 3335 if the (S,G) assert state machine is in NoInfo state: 3337 Receive Inferior Assert with RPTbit set AND 3338 CouldAssert(*,G,I)==TRUE 3339 An Inferior (*,G) assert is received for G on Interface I. If 3340 CouldAssert(*,G,I) is TRUE, then I is our downstream 3341 interface, and we have (*,G) forwarding state on this 3342 interface, so we should be the assert winner. We transition 3343 to the "I am Assert Winner" state, and perform Actions A1 3344 (below). 3346 A data packet destined for G arrives on interface I, AND 3347 CouldAssert(*,G,I)==TRUE 3348 A data packet destined for G arrived on a downstream interface 3349 which is in our (*,G) outgoing interface list. We therefore 3350 believe we should be the forwarder for this (*,G), and so we 3351 transition to the "I am Assert Winner" state, and perform 3352 Actions A1 (below). 3354 Receive Preferred Assert with RPT bit set AND 3355 AssertTrackingDesired(*,G,I)==TRUE 3356 We're interested in (*,G) Asserts, either because I is a 3357 downstream interface for which we have (*,G) forwarding state, 3358 or because I is the upstream interface for RP(G) and we have 3359 (*,G) forwarding state. We get a (*,G) Assert that has a 3360 better metric than our own, so we do not win the Assert. We 3361 transition to "I am Assert Loser" and perform actions A2 3362 (below). 3364 Transitions from Winner State 3366 When in "I am Assert Winner" state, the following events trigger 3367 transitions, but only if the (S,G) assert state machine is in NoInfo 3368 state: 3370 Receive Inferior Assert 3371 We receive a (*,G) assert that has a worse metric than our 3372 own. Whoever sent the assert has lost, and so we re-send a 3373 (*,G) Assert, and restart the timer (Action A3 below). 3375 Receive Preferred Assert 3376 We receive a (*,G) assert that has a better metric than our 3377 own. We transition to "I am Assert Loser" state and perform 3378 actions A2 (below). 3380 When in "I am Assert Winner" state, the following events trigger 3381 transitions: 3383 Timer Expires 3384 The (*,G) assert timer expires. As we're in the Winner state, 3385 then we must still have (*,G) forwarding state that is 3386 actively being kept alive. To prevent unnecessary thrashing 3387 of the forwarder and periodic flooding of duplicate packets, 3388 we re-send the (*,G) Assert, and restart the timer (Action A3 3389 below). 3391 CouldAssert(*,G,I) -> FALSE 3392 Our (*,G) forwarding state or RPF interface changed so as to 3393 make CouldAssert(*,G,I) become false. We can no longer 3394 perform the actions of the assert winner, and so we transition 3395 to NoInfo state and perform actions A4 (below). 3397 Transitions from Loser State 3399 When in "I am Assert Loser" state, the following events trigger 3400 transitions, but only if the (S,G) assert state machine is in NoInfo 3401 state: 3403 Receive Preferred Assert 3404 We receive a (*,G) assert that is better than that of the 3405 current assert winner. We stay in Loser state, and perform 3406 actions A2 below. 3408 Receive Inferior Assert from Current Winner 3409 We receive an assert from the current assert winner that is 3410 worse than our own metric for this group (typically because 3411 the winner's metric became worse). We transition to NoInfo 3412 state, delete this (*,G) assert state, and allow the normal 3413 PIM Join/Prune mechanisms to operate. Usually we will 3414 eventually re-assert and win when data packets for G have 3415 started flowing again. 3417 When in "I am Assert Loser" state, the following events trigger 3418 transitions: 3420 Timer Expires 3421 The (*,G) assert timer expires. We transition to NoInfo state 3422 and delete this (*,G) assert info. 3424 AssertTrackingDesired(*,G,I)->FALSE 3425 AssertTrackingDesired(*,G,I) becomes FALSE. Our forwarding 3426 state has changed so that (*,G) Asserts on interface I are no 3427 longer of interest to us. We transition to NoInfo state and 3428 delete this (*,G) assert info. 3430 My metric becomes better than the assert winner's metric 3431 My routing metric, rpt_assert_metric(G,I), has changed so that | 3432 now my assert metric for (*,G) is better than the metric we | 3433 have stored for current assert winner. We transition to | 3434 NoInfo state, and delete this (*,G) assert state, and allow | 3435 the normal PIM Join/Prune mechanisms to operate. Usually we | 3436 will eventually re-assert and win when data packets for G have | 3437 started flowing again. | 3439 RPF interface changed away from interface I 3440 Interface I used to be the RPF interface for RP(G), and now it 3441 is not. We transition to NoInfo state, and delete this (*,G) 3442 assert state. 3444 Receive Join(*,G) or Join(*,*,RP(G)) 3445 We receive a Join(*,G) or a Join(*,*,RP(G)) directed to my IP 3446 address in interface I. The action is to transition to NoInfo 3447 state, and delete this (*,G) assert state, and allow the 3448 normal PIM Join/Prune mechanisms to operate. If whoever sent 3449 the Join was in error, then the normal assert mechanism will 3450 eventually re-apply and we will lose the assert again. 3451 However whoever sent the assert may know that the previous 3452 assert winner has died, and so we may end up being the new 3453 forwarder. 3455 (*,G) Assert State-machine Actions 3457 A1: Send Assert(*,G) 3458 Set timer to (Assert_Time - Assert_Override_Interval) 3459 Store self as AssertWinner(*,G) 3461 A2: Store new AssertWinner(*,G) 3462 Set timer to assert_time 3464 A3: Send Assert(*,G) 3465 Set timer to (Assert_Time - Assert_Override_Interval) 3467 A4: Send AssertCancel(*,G) 3468 Delete assert info 3470 A5: Delete assert info 3472 4.5.3. Assert Metrics 3474 Assert metrics are defined as: 3476 struct assert_metric { 3477 rpt_bit_flag; 3478 metric_preference; 3479 route_metric; 3480 ip_address; 3481 }; 3483 When comparing assert_metrics, the rpt_bit_flag, metric_preference, and 3484 route_metric field are compared in order, where the first lower value 3485 wins. If all fields are equal, the IP address of the router that 3486 sourced the Assert message is used as a tie-breaker, with the highest IP 3487 address winning. 3489 An assert metric for (S,G) to include in (or compare against) an Assert 3490 message sent on interface I should be computed using the following 3491 pseudocode: 3493 assert_metric 3494 my_assert_metric(S,G,I) { 3495 if( CouldAssert(S,G,I) == TRUE ) { 3496 return spt_assert_metric(S,G,I) 3497 } else if( CouldAssert(*,G,I) == TRUE ) { 3498 return rpt_assert_metric(G,I) 3499 } else { 3500 return infinite_assert_metric() 3501 } 3502 } 3504 spt_assert_metric(S,I) gives the assert metric we use if we're sending 3505 an assert based on active (S,G) forwarding state: 3507 assert_metric 3508 spt_assert_metric(S,I) { 3509 return {0,MRIB.pref(S),MRIB.metric(S),my_ip_address(I)} 3510 } 3512 rpt_assert_metric(G,I) gives the assert metric we use if we're sending 3513 an assert based only on (*,G) forwarding state: 3515 assert_metric 3516 rpt_assert_metric(G,I) { 3517 return {1,MRIB.pref(RP(G)),MRIB.metric(RP(G)),my_ip_address(I)} 3518 } 3520 MRIB.pref(X) and MRIB.metric(X) are the routing preference and routing 3521 metrics associated with the route to a particular (unicast) destination 3522 X, as determined by the MRIB. my_ip_address(I) is simply the router's 3523 IP address that is associated with the local interface I. 3525 infinite_assert_metric() gives the assert metric we need to send an 3526 assert but don't match either (S,G) or (*,G) forwarding state: 3528 assert_metric 3529 infinite_assert_metric() { 3530 return {1,infinity,infinity,infinity} 3531 } 3533 4.5.4. AssertCancel Messages 3535 An AssertCancel message is simply an RPT Assert message but with 3536 infinite metric. It is sent by the assert winner when it deletes the 3537 forwarding state that had caused the assert to occur. Other routers 3538 will see this metric, and it will cause any other router that has 3539 forwarding state to send its own assert, and to take over forwarding. 3541 An AssertCancel(S,G) is an infinite metric assert with the RPT bit set 3542 that names S as the source. 3544 An AssertCancel(*,G) is an infinite metric assert with the RPT bit set, 3545 and typically will name RP(G) as the source as it cannot name an 3546 appropriate S. 3548 AssertCancel messages are simply an optimization. The original Assert 3549 timeout mechanism will allow a subnet to eventually become consistent; 3550 the AssertCancel mechanism simply causes faster convergence. No special 3551 processing is required for an AssertCancel message, since it is simply 3552 an Assert message from the current winner. 3554 4.5.5. Assert State Macros 3556 The macros lost_assert(S,G,rpt,I), lost_assert(S,G,I), and 3557 lost_assert(*,G,I) are used in the olist computations of Section 4.1, 3558 and are defined as: 3560 bool lost_assert(S,G,rpt,I) { 3561 if ( RPF_interface(RP) == I OR | 3562 ( RPF_interface(S) == I AND SPTbit(S,G) == TRUE ) ) { | 3563 return FALSE | 3564 } else { | 3565 return ( AssertWinner(S,G,I) != me ) | 3566 } | 3567 } | 3569 bool lost_assert(S,G,I) { 3570 if ( RPF_interface(S) == I ) { 3571 return FALSE 3572 } else { 3573 return ( AssertWinner(S,G,I) != me AND 3574 (AssertWinnerMetric(S,G,I) is better 3575 than spt_assert_metric(S,G,I) ) 3576 } 3577 } 3578 bool lost_assert(*,G,I) { 3579 if ( RPF_interface(RP) == I ) { 3580 return FALSE 3581 } else { 3582 return ( AssertWinner(*,G,I) != me ) 3583 } 3584 } 3586 AssertWinner(S,G,I) defaults to Null and AssertWinnerMetric(S,G,I) 3587 defaults to Infinity when in the NoInfo state. 3589 Rationale for Assert Rules 3591 The following is a summary of the rules for sending and reacting to 3592 asserts. It is not intended to be definitive (the state machines and 3593 pseudocode provide the definitive behavior). Instead it provides some 3594 rationale for the behavior. 3596 1. Downstream neighbors send Join(*,G) and Join(S,G) periodic messages 3597 to the appropriate RPF' neighbor, i.e., the RPF neighbor as 3598 modified by the assert process. Normal suppression and override 3599 rules apply. 3601 This guarantees that all requested traffic will continue to arrive. 3602 This doesn't allow switching back to the "normal" RPF neighbor 3603 until the assert times out, which it won't while data is flowing if 3604 we are implementing rule 8. 3606 2. The assert winner for (*,G) acts as the local DR for (*,G) on 3607 behalf of IGMP members. 3609 This is required to allow a single router to merge PIM and IGMP 3610 joins and leaves. Without this, overrides don't work. 3612 3. The assert winner for (S,G) must act as the local DR for (S,G) on 3613 behalf of IGMPv3 members. 3615 Same rationale as (2) 3617 4. (S,G) and (*,G) prune overrides are sent to the RPF' neighbor and 3618 not to the regular RPF neighbor. 3620 Same rationale as (1). 3622 5. An (S,G,rpt) prune override is not sent (at all) if RPF'(S,G,rpt) 3623 != RPF'(*,G). 3625 This avoids keeping state alive on (S,G) tree when only (*,G) 3626 downstream members are left. Also, it avoids sending (S,G,rpt) 3627 joins to a router that is not on the (*,G) tree. This might be 3628 confusing and could be interpreted as being undefined although 3629 technically the current spec says to drop such a join. 3631 6. An assert loser that receives a Join(S,G) directed to it cancels 3632 the (S,G) assert timer. 3634 7. An assert loser that receives a Join(*,G) or a Join(*,*,RP(G)) 3635 directed to it cancels the (*,G) assert timer and all (S,G) assert 3636 timers that do not have corresponding Prune(S,G,rpt) messages in 3637 the compound Join/Prune message. 3639 Rules 7 and 8 help convergence during topology changes. 3641 8. An assert winner for (*,G) or (S,G) sends a canceling assert when 3642 it is about to stop forwarding on a (*,G) or an (S,G) entry. This 3643 rule does not apply to (S,G,rpt). 3645 This allow switching back to the shared tree after the last SPT 3646 router on the lan leaves. We don't want RPT downstream routers to 3647 keep SPT state alive. 3649 9. [Optionally] re-assert before timing out. 3651 This prevents periodic duplicates. 3653 10. When RPF'(S,G,rpt) changes to be the same as RPF'(*,G) we need to 3654 trigger a Join(S,G,rpt) to RPF(*,G). 3656 This allows switching back to the RPT after the last SPT member 3657 leaves. 3659 4.6. Designated Routers (DR) and Hello Messages 3661 4.6.1. Sending Hello Messages 3663 PIM-Hello messages are sent periodically on each PIM-enabled interface. 3664 They allow a router to learn about the neighboring PIM routers on each 3665 interface. Hello messages are also the mechanism used to elect a 3666 Designated Router (DR). A router must record the Hello information 3667 received from each PIM neighbor. 3669 Hello messages are sent periodically on each PIM-enabled interface. 3670 Hello messages are multicast to address 224.0.0.13 (the ALL-PIM-ROUTERS 3671 group). Hello messages must be sent on all active interfaces, including 3672 physical point-to-point links. When PIM is enabled on an interface or a 3673 router first starts, the hello timer is set to a random value between 0 3674 and Triggered_Hello_Delay to prevent synchronization of Hello messages | 3675 if multiple routers are powered on simultaneously. After the initial | 3676 randomized interval, Hello messages must be sent every Hello_Period 3677 seconds. A single hello timer is used to trigger sending Hello messages 3678 on all active interfaces. The hello timer should not be reset except 3679 when it expires. 3681 The DR Election Priority Option allows a network administrator to give 3682 preference to a particular router in the DR election process by giving 3683 it a numerically larger DR Election Priority. The DR Election Priority 3684 Option SHOULD be included in every Hello message, even if no DR election 3685 priority is explicitly configured on that interface. This is necessary 3686 because priority-based DR election is only enabled when all neighbors on 3687 an interface advertise that they are capable of using the DR Election 3688 Priority Option. The default priority is 1. 3690 The Generation Identifier (GenID) Option SHOULD be included in all Hello 3691 messages. The generation ID option contains a randomly generated 32-bit 3692 value that is regenerated each time PIM forwarding is started or 3693 restarted on the interface, including when the router itself restarts. 3694 When a Hello message with a new GenID is received from a neighbor, any 3695 old Hello information about that neighbor SHOULD be discarded and 3696 superseded by the information from the new Hello message. This may 3697 cause a new DR to be chosen on that interface. | 3699 To allow new or rebooting routers to learn of PIM neighbors quickly, | 3700 when a Hello message is received from a new neighbor, or a Hello message | 3701 with a new GenID is received from an existing neighbor, a new Hello | 3702 message should be sent on this interface after a randomized delay | 3703 between 0 and Triggered_Hello_Delay. This triggered message need not | 3704 change the timing of the scheduled periodic message. | 3706 When an interface goes down or changes IP address, a Hello message with 3707 a zero Hold Time should be sent immediately (with the old IP address if 3708 the IP address changed). This will cause PIM neighbors to remove this 3709 neighbor (or its old IP address) immediately. 3711 4.6.2. DR Election 3713 When a PIM-Hello message is received on interface I the following 3714 information about the sending neighbor is recorded: 3716 neighbor.interface 3717 The interface on which the Hello message arrived. 3719 neighbor.ip_address 3720 The IP address of the PIM neighbor. 3722 neighbor.genid 3723 The Generation ID of the PIM neighbor. 3725 neighbor.dr_priority 3726 The DR Priority field of the PIM neighbor if it is present in 3727 the Hello message. 3729 neighbor.dr_priority_present 3730 A flag indicating if the DR Priority field was present in the 3731 Hello message. 3733 neighbor.timeout 3734 A timer to time out the neighbor state when it becomes stale. 3735 This is reset to Hello Holdtime whenever a Hello message is 3736 received, or to the value specified in the message, if the 3737 hold time option is used. 3739 Neighbor state is deleted when the neighbor timeout expires. 3741 The function for computing the DR on interface I is: 3743 host 3744 DR(I) { 3745 dr = me 3746 for each neighbor on interface I { 3747 if ( dr_is_better( neighbor, dr, I ) == TRUE ) { 3748 dr = neighbor 3749 } 3750 } 3751 return dr 3752 } 3754 The function used for comparing DR "metrics" on interface I is: 3756 bool 3757 dr_is_better(a,b,I) { 3758 if( there is a neighbor n on I for which n.dr_priority_present 3759 is false ) { 3760 return a.ip_address > b.ip_address 3761 } else { 3762 return ( a.dr_priority > b.dr_priority ) OR 3763 ( a.dr_priority == b.dr_priority AND 3764 a.ip_address > b.ip_address ) 3765 } 3766 } 3768 The DR election priority is a 32-bit unsigned number and the numerically 3769 larger priority is always preferred. A router's idea of the current DR 3770 on an interface can change when a PIM-Hello message is received, when a 3771 neighbor times out, or when a router's own DR priority changes. If the | 3772 router becomes the DR or ceases to be the DR, this will normally cause | 3773 the DR Register state-machine to change state. Subsequent actions are 3774 determined by that state-machine. 3776 4.7. PIM Bootstrap and RP Discovery 3778 For correct operation, every PIM router within a PIM domain must be able | 3779 to map a particular multicast group address to the same RP. If this is | 3780 not the case then black holes may appear, where some receivers in the | 3781 domain cannot receive some groups. A domain in this context is a | 3782 contiguous set of routers that all implement PIM and are configured to | 3783 operate within a common boundary defined by PIM Multicast Border Routers | 3784 (PMBRs). PMBRs connect each PIM domain to the rest of the Internet. | 3786 A notable exception to this is where a PIM domain is broken up into | 3787 multiple administrative scope regions - these are regions where a border | 3788 has been configured so that a range of multicast groups will not be | 3789 forwarded across that border. For more information on Administratively | 3790 Scoped IP Multicast, see RFC 2365. The modified criteria for admin- | 3791 scoped regions are that the region is convex with respect to forwarding | 3792 based on the MRIB, and that all PIM routers within the scope region map | 3793 scoped groups to the same RP within that region. | 3795 This specification does not mandate the use of a single mechanism to | 3796 provide routers with the information to perform the group-to-RP mapping. | 3797 Currently three mechanisms are possible, and all three have associated | 3798 problems: | 3800 Static Configuration | 3801 A PIM router MUST support the static configuration of group-to-RP | 3802 mappings. Such a mechanism is not robust to failures, but does at | 3803 least provide a basic interoperability mechanism. | 3805 Cisco's Auto-RP | 3806 Auto-RP uses a PIM Dense-Mode multicast group to announce group-to- | 3807 RP mappings from a central location. This mechanism is not useful | 3808 if PIM Dense-Mode is not being run in parallel with PIM Sparse- | 3809 Mode, and was only intended for use with PIM Sparse-Mode Version 1. | 3810 No standard specification currently exists. | 3812 BootStrap Router (BSR) | 3813 RFC 2362 specifies a bootstrap mechanism based around the automatic | 3814 election of a bootstrap router (BSR). Any router in the domain | 3815 that is configured to be a possible RP reports its candidacy to the | 3816 BSR, and then a domain-wide flooding mechanism distributes the | 3817 BSR's chosen set of RPs throughout the domain. As specified in RFC | 3818 2362, BSR is flawed in its handling of admin-scoped regions that | 3819 are smaller than a PIM domain, but the mechanism does work for | 3820 global-scoped groups. | 3822 As far as PIM-SM is concerned, the only important requirement is that | 3823 all routers in the domain (or admin scope zone for scoped regions) | 3824 receive the same set of group-range-to-RP mappings. This may be | 3825 achieved through the use of any of these mechansms, or through | 3826 alternative mechanisms not currently specified. | 3828 Any RP address configured or learned MUST be a domain-wide reachable | 3829 address. | 3831 4.7.1. Group-to-RP Mapping 3833 Using one of the mechanisms described above, a PIM router receives one | 3834 or more possible group-range-to-RP mappings. Each mapping specifies a | 3835 range of multicast groups (expressed as a group and mask) and the RP to | 3836 which such groups should be mapped. Each mapping may also have an | 3837 associated priority. It is possible to receive multiple mappings all of | 3838 which might match the same multicast group - this is the common case | 3839 with BSR. The algorithm for performing the group-to-RP mapping is as | 3840 follows: | 3842 1 Perform longest match on group-range to obtain a list of RPs. | 3844 2 From this list of matching RPs, find the one with highest priority. | 3845 Eliminate any RPs from the list that have lower priorities. | 3847 3 If only one RP remains in the list, use that RP. | 3848 4 If multiple RPs are in the list, use the PIM hash function to | 3849 choose one. | 3851 Thus if two or more group-range-to-RP mappings cover a particular group, | 3852 the one with the longest mask is the mapping to use. If the mappings | 3853 have the same mask length, then the one with the highest priority is | 3854 chosen. If there is more than one matching entry with the same longest | 3855 mask and the priorities are identical, then a hash function (see Section | 3856 4.7.2) is applied to choose the RP. | 3858 This algorithm is invoked by a DR when it needs to determine an RP for a | 3859 given group, e.g. upon reception of a packet or IGMP membership | 3860 indication for a group for which the DR does not know the RP. It is | 3861 invoked by any router that has (*,*,RP) state when a packet is received | 3862 for which there is no corresponding (S,G) or (*,G) entry. Furthermore, | 3863 the mapping function is invoked by all routers upon receiving a (*,G) or | 3864 (*,*,RP) Join/Prune message. | 3866 Note that if the set of possible group-range-to-RP mappings changes, | 3867 each router will need to check whether any existing groups are affected. | 3868 This may, for example, cause a DR or acting DR to re-join a group, or | 3869 cause it to re-start register encapsulation to the new RP. | 3871 4.7.2. Hash Function 3873 The hash function is used by all routers within a domain, to map a group | 3874 to one of the RPs from the matching set of group-range-to-RP mappings | 3875 (this set all have the same longest mask length and same highest | 3876 priority). The algorithm takes as input the group address, and the | 3877 addresses of the candidate RPs from the mappings, and gives as output | 3878 one RP address to be used. | 3879 The protocol requires that all routers hash to the same RP within a 3880 domain (except for transients). The following hash function must be used 3881 in each router: 3883 1 For RP addresses in the matching group-range-to-RP mappings, | 3884 compute a value: | 3886 Value(G,M,C(i))= 3887 (1103515245 * ((1103515245 * (G&M)+12345) XOR C(i)) + 12345) mod 2^31 3889 where C(i) is the RP address and M is a hash-mask included in 3890 Bootstrap messages. The hash-mask allows a small number of 3891 consecutive groups (e.g., 4) to always hash to the same RP. For 3892 instance, hierarchically-encoded data can be sent on consecutive 3893 group addresses to get the same delay and fate-sharing 3894 characteristics. 3896 For address families other than IPv4, a 32-bit digest to be used as | 3897 C(i) and G must first be derived from the actual RP or group | 3898 address. Such a digest method must be used consistently throughout | 3899 the PIM domain. For IPv6 addresses, we recommend using the 3900 equivalent IPv4 address for an IPv4-compatible address, and the | 3901 exclusive-or of each 32-bit segment of the address for all other | 3902 IPv6 addresses. For example, the digest of the IPv6 address | 3903 3ffe:b00:c18:1::10 would be computed as 0x3ffe0b00 ^ 0x0c180001 ^ | 3904 0x00000000 ^ 0x00000010, where ^ represents the exclusive-or | 3905 operation. | 3907 2 The candidate RP with the highest resulting hash value is then | 3908 chosen as the RP for that group, and its identity and hash value 3909 are stored with the entry created. 3911 Ties between RPs having the same hash value are broken in advantage | 3912 of the highest address. 3914 4.8. Source-Specific Multicast 3916 The Source-Specific Multicast (SSM) service model [11] can be 3917 implemented with a strict subset of the PIM-SM protocol mechanisms. 3918 Both regular IP Multicast and SSM semantics can coexist on a single 3919 router and both can be implemented using the PIM-SM protocol. A range 3920 of multicast addresses, currently 232.0.0.0/8 in IPv4, is reserved for 3921 SSM, and the choice of semantics is determined by the multicast group 3922 address in both data packets and PIM messages. 3924 4.8.1. Protocol Modifications for SSM destination addresses 3926 The following rules override the normal PIM-SM behavior for a multicast 3927 address G in the SSM reserved range: 3929 o A router MUST NOT send a (*,G) Join/Prune message for any reason. 3931 o A router MUST NOT send an (S,G,rpt) Join/Prune message for any reason. 3933 o A router MUST NOT send a Register message for any packet that is 3934 destined to an SSM address. 3936 o A router MUST NOT forward packets based on (*,G) or (S,G,rpt) state. 3937 The (*,G) and (S,G,rpt) -related state summarization macros are NULL 3938 for any SSM address, for the purposes of packet forwarding. 3940 o A router acting as an RP MUST NOT forward any Register-encapsulated 3941 packet that has an SSM destination address. 3943 The last two rules are present to deal with "legacy" routers unaware of 3944 SSM that may be sending (*,G) and (S,G,rpt) Join/Prunes, or Register 3945 messages for SSM destination addresses. 3947 Additionally: 3949 o A router MAY be configured to advertise itself as a Candidate RP for 3950 an SSM address. If so, it SHOULD respond with a Register-Stop message 3951 to any Register message containing a packet destined for an SSM 3952 address. 3954 o A router MAY optimize out the creation and maintenance of (S,G,rpt) 3955 and (*,G) state for SSM destination addresses -- this state is not 3956 needed for SSM packets. 3958 4.8.2. PIM-SSM-only Routers 3960 An implementor may choose to implement only the subset of PIM Sparse- 3961 Mode that provides SSM forwarding semantics. 3963 A PIM-SSM-only router MUST implement the following portions of this 3964 specification: 3966 o Upstream (S,G) state machine (Section 4.4.7) 3968 o Downstream (S,G) state machine (Section 4.4.3) 3970 o (S,G) Assert state machine (Section 4.5.1) 3972 o Hello messages, neighbor discovery and DR election (Section 4.6) 3974 o Packet forwarding rules (Section 4.2) 3976 A PIM-SSM-only router does not need to implement the following protocol 3977 elements: 3979 o Register state machine (Section 4.3) 3981 o (*,G), (S,G,rpt) and (*,*,RP) Downstream state machines (Sections 3982 4.4.2, 4.4.4, and 4.4.1) 3984 o (*,G), (S,G,rpt), and (*,*,RP) Upstream state machines (Sections 3985 4.4.6, 4.4.8, and 4.4.5) 3987 o (*,G) Assert state machine (Section 4.5.2) 3989 o Bootstrap RP Election (Section 4.7) 3991 o Keepalive Timer 3993 o SptBit (Section 4.2.1) 3995 The KeepaliveTimer should be treated as always running and SptBit should 3996 be treated as being always set for an SSM address. Additionally, the 3997 Packet forwarding rules of Section 4.2 can be simplified in a PIM-SSM- 3998 only router: 4000 if( iif == RPF_interface(S) AND UpstreamJPState(S,G) == Joined ) { 4001 oiflist = inherited_olist(S,G) 4002 } else if( iif is in inherited_olist(S,G) ) { 4003 send Assert(S,G) on iif 4004 } 4006 oiflist = oiflist (-) iif 4007 forward packet on all interfaces in oiflist 4009 This is nothing more than the reduction of the normal PIM-SM forwarding 4010 rule, with all (S,G,rpt) and (*,G) clauses replaced with NULL. 4012 4.9. PIM Packet Formats 4014 This section describes the details of the packet formats for PIM control 4015 messages. 4017 All PIM control messages have IP protocol number 103. | 4019 PIM messages are either unicast (e.g. Registers and Register-Stop), or | 4020 multicast with TTL 1 to the `ALL-PIM-ROUTERS' group (e.g. Join/Prune, | 4021 Asserts, etc.). The source address used for unicast messages is a | 4022 domain-wide reachable address; the source address used for multicast | 4023 messages is the link-local address of the interface on which the message | 4024 is being sent. | 4026 The IPv4 `ALL-PIM-ROUTERS' group is `224.0.0.13'. The IPv6 `ALL-PIM- | 4027 ROUTERS' group is `ff02::d'. | 4028 0 1 2 3 4029 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 4030 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4031 |PIM Ver| Type | Reserved | Checksum | 4032 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4034 PIM Ver 4035 PIM Version number is 2. 4037 Type Types for specific PIM messages. PIM Types are: 4039 0 = Hello 4040 1 = Register 4041 2 = Register-Stop 4042 3 = Join/Prune 4043 4 = Bootstrap 4044 5 = Assert 4045 6 = Graft (used in PIM-DM only) 4046 7 = Graft-Ack (used in PIM-DM only) 4047 8 = Candidate-RP-Advertisement 4049 Reserved 4050 Set to zero on transmission. Ignored upon receipt. 4052 Checksum 4053 The checksum is a standard IP checksum, i.e. the 16-bit one's | 4054 complement of the one's complement sum of the entire PIM message, 4055 excluding the data portion in the Register message. For computing 4056 the checksum, the checksum field is zeroed. | 4058 For IPv6, the checksum also includes the IPv6 "pseudo-header", as | 4059 specified in RFC 2460, section 8.1 [8]. This "pseudo-header" is | 4060 prepended to the PIM header for the purposes of calculating the | 4061 checksum. The "Upper-Layer Packet Length" in the pseudo-header is | 4062 set to the length of the PIM message. The Next Header value used | 4063 in the pseudo-header is 103. If the packet's length is not an | 4064 integral number of 16-bit words, the packet is padded with a byte | 4065 of zero before performing the checksum. | 4067 4.9.1. Encoded Source and Group Address Formats 4069 Encoded-Unicast address 4071 An Encoded-Unicast address takes the following format: 4073 0 1 2 3 4074 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 4075 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4076 | Addr Family | Encoding Type | Unicast Address 4077 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+... 4079 Addr Family 4080 The PIM address family of the `Unicast Address' field of this | 4081 address. 4083 Values of 0-127 are as assigned by the IANA for Internet Address 4084 Families in [5]. Values 128-250 are reserved to be assigned by the 4085 IANA for PIM-specific Address Families. Values 251 though 255 are 4086 designated for private use. As there is no assignment authority 4087 for this space, collisions should be expected. 4089 Encoding Type 4090 The type of encoding used within a specific Address Family. The 4091 value `0' is reserved for this field, and represents the native 4092 encoding of the Address Family. 4094 Unicast Address 4095 The unicast address as represented by the given Address Family and 4096 Encoding Type. 4098 Encoded-Group address 4100 Encoded-Group addresses take the following format: 4102 0 1 2 3 4103 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 4104 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4105 | Addr Family | Encoding Type | Reserved | Mask Len | 4106 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4107 | Group multicast Address 4108 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+... 4110 Addr Family 4111 described above. 4113 Encoding Type 4114 described above. 4116 Reserved 4117 Transmitted as zero. Ignored upon receipt. 4119 Mask Len 4120 The Mask length field is 8 bits. The value is the number of 4121 contiguous one bits left justified used as a mask which, combined 4122 with the group address, describes a range of groups. It is less 4123 than or equal to the address length in bits for the given Address 4124 Family and Encoding Type. If the message is sent for a single group 4125 then the Mask length must equal the address length in bits for the 4126 given Address Family and Encoding Type. (e.g. 32 for IPv4 native 4127 encoding and 128 for IPv6 native encoding). 4129 Group multicast Address 4130 Contains the group address. 4132 Encoded-Source address 4134 Encoded-Source address takes the following format: 4136 0 1 2 3 4137 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 4138 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4139 | Addr Family | Encoding Type | Rsrvd |S|W|R| Mask Len | 4140 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4141 | Source Address 4142 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-... 4144 Addr Family 4145 described above. 4147 Encoding Type 4148 described above. 4150 Reserved 4151 Transmitted as zero, ignored on receipt. 4153 S The Sparse bit is a 1 bit value, set to 1 for PIM-SM. It is used 4154 for PIM version 1 compatibility. 4156 W The WC (or WildCard) bit is a 1 bit value for use with PIM | 4157 Join/Prune messages (see section 4.9.5.1 ). | 4159 R The RPT (or Rendezvous Point Tree) bit is a 1 bit value for use | 4160 with PIM Join/Prune messages (see section 4.9.5.1 ). If the WC bit | 4161 is 1, the RPT bit MUST be 1. | 4163 Mask Len 4164 The mask length field is 8 bits. The value is the number of 4165 contiguous one bits left justified used as a mask which, combined 4166 with the Source Address, describes a source subnet. The mask length 4167 must be less than or equal to the address length in bits for the 4168 given Address Family and Encoding Type. If the message is sent for 4169 a single source then the Mask length must equal the address length 4170 in bits for the given Address Family and Encoding Type. In version 4171 2 of PIM, it is strongly recommended that this field be set to 32 4172 for IPv4 native encoding. 4174 Source Address 4175 The source address. 4177 4.9.2. Hello Message Format 4179 It is sent periodically by routers on all interfaces. 4181 0 1 2 3 4182 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 4183 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4184 |PIM Ver| Type | Reserved | Checksum | 4185 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4186 | OptionType | OptionLength | 4187 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4188 | OptionValue | 4189 | ... | 4190 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4191 | . | 4192 | . | 4193 | . | 4194 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4195 | OptionType | OptionLength | 4196 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4197 | OptionValue | 4198 | ... | 4199 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4201 PIM Version, Type, Reserved, Checksum 4202 Described above. 4204 OptionType 4205 The type of the option given in the following OptionValue field. 4207 OptionLength 4208 The length of the OptionValue field in bytes. 4210 OptionValue 4211 A variable length field, carrying the value of the option. 4213 The Option fields may contain the following values: 4215 o OptionType 1: Hold Time 4216 0 1 2 3 4217 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 4218 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4219 | Type = 1 | Length = 2 | 4220 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4221 | Hold Time | 4222 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4224 Hold Time is the amount of time a receiver must keep the neighbor 4225 reachable, in seconds. If the Holdtime is set to `0xffff', the 4226 receiver of this message never times out the neighbor. This may 4227 be used with dial-on-demand links, to avoid keeping the link up 4228 with periodic Hello messages. Furthermore, if the Holdtime is 4229 set to `0', the information is timed out immediately. 4231 o OptionType 2 to 16: reserved to be defined in future versions of 4232 this document. 4234 o OptionType 18: deprecated and should not be used. 4236 o OptionType 19: DR Priority 4238 0 1 2 3 4239 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 4240 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4241 | Type = 19 | Length = 4 | 4242 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4243 | DR Priority | 4244 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4246 DR Priority is a 32-bit unsigned number and should be considered 4247 in the DR election as described in section 4.6.2. 4249 o OptionType 20: Generation ID 4251 0 1 2 3 4252 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 4253 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4254 | Type = 20 | Length = 4 | 4255 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4256 | Generation ID | 4257 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4259 Generation ID is a random 32-bit value for the interface on which 4260 the Hello message is sent. The Generation ID is regenerated 4261 whenever PIM forwarding is started or restarted on the interface. 4263 OptionTypes 17 thru 65000 are assigned by the IANA. OptionTypes 4264 65001 through 65535 are reserved for Private Use, as defined in 4265 [6]. 4266 Unknown options may be ignored. The "Hold Time" option MUST be 4267 implemented; the "DR Priority" and "Generation ID" options SHOULD 4268 be implemented. 4270 4.9.3. Register Message Format 4272 A Register message is sent by the DR or a PMBR to the RP when a | 4273 multicast packet needs to be transmitted on the RP-tree. The IP source | 4274 address is set to the address of the DR, the destination address to the | 4275 RP's address. The IP TTL of the PIM packet is the system's normal | 4276 unicast TTL. | 4278 0 1 2 3 4279 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 4280 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4281 |PIM Ver| Type | Reserved | Checksum | 4282 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4283 |B|N| Reserved2 | | 4284 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 4285 | | | 4286 . Multicast data packet . | 4287 | | | 4288 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 4290 PIM Version, Type, Reserved, Checksum 4291 Described above. Note that the checksum for Registers is done only 4292 on first 8 bytes of packet, including the PIM header and the next 4 4293 bytes, excluding the data packet portion. For interoperability 4294 reasons, a message carrying a checksum calculated over the entire 4295 PIM register message should be accepted. 4297 B The Border bit. If the router is a DR for a source that it is 4298 directly connected to, it sets the B bit to 0. If the router is a 4299 PMBR for a source in a directly connected cloud, it sets the B bit 4300 to 1. 4302 N The Null-Register bit. Set to 1 by a DR that is probing the RP 4303 before expiring its local Register-Suppression timer. Set to 0 4304 otherwise. 4306 Reserved2 4307 Transmitted as zero, ignored on receipt. 4309 Multicast data packet 4310 The original packet sent by the source. This packet must be the of 4311 the same address family as the encapsulating PIM packet, e.g. an 4312 IPv6 data packet must be encapsulated in an IPv6 PIM packet. Note | 4313 that the TTL of the original packet is decremented before | 4314 encapsulation, just like any other packet that is forwarded. In | 4315 addition, the RP decrements the TTL after decapsulating, before | 4316 forwarding the packet down the shared tree. | 4318 For (S,G) null Registers, the Multicast data packet portion 4319 contains only a dummy header with S as the source address, G as the 4320 destination address, and a data length of zero. 4322 4.9.4. Register-Stop Message Format 4324 A Register-Stop is unicast from the RP to the sender of the Register 4325 message. The IP source address is the address to which the register was 4326 addressed. The IP destination address is the source address of the 4327 register message. 4329 0 1 2 3 4330 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 4331 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4332 |PIM Ver| Type | Reserved | Checksum | 4333 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4334 | Group Address (Encoded-Group format) | 4335 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4336 | Source Address (Encoded-Unicast format) | 4337 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4339 PIM Version, Type, Reserved, Checksum 4340 Described above. 4342 Group Address 4343 The group address from the multicast data packet in the Register. 4344 Format described in section 4.9.1. Note that for Register-Stops the 4345 Mask Len field contains the full address length * 8 (e.g. 32 for 4346 IPv4 native encoding), if the message is sent for a single group. 4348 Source Address 4349 Host address of source from multicast data packet in register. The 4350 format for this address is given in the Encoded-Unicast address in 4351 section 4.9.1. A special wild card value (0's), can be used to 4352 indicate any source. XXX note that "(0's)" doesn't really describe 4353 what the rest of the field in encoded-unicast-address should be 4355 4.9.5. Join/Prune Message Format 4357 A Join/Prune message is sent by routers towards upstream sources and 4358 RPs. Joins are sent to build shared trees (RP trees) or source trees 4359 (SPT). Prunes are sent to prune source trees when members leave groups 4360 as well as sources that do not use the shared tree. 4362 0 1 2 3 4363 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 4364 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4365 |PIM Ver| Type | Reserved | Checksum | 4366 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4367 | Upstream Neighbor Address (Encoded-Unicast format) | 4368 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4369 | Reserved | Num groups | Holdtime | 4370 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4371 | Multicast Group Address 1 (Encoded-Group format) | 4372 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4373 | Number of Joined Sources | Number of Pruned Sources | 4374 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4375 | Joined Source Address 1 (Encoded-Source format) | 4376 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4377 | . | 4378 | . | 4379 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4380 | Joined Source Address n (Encoded-Source format) | 4381 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4382 | Pruned Source Address 1 (Encoded-Source format) | 4383 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4384 | . | 4385 | . | 4386 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4387 | Pruned Source Address n (Encoded-Source format) | 4388 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4389 | . | 4390 | . | 4391 | . | 4392 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4393 | Multicast Group Address m (Encoded-Group format) | 4394 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4395 | Number of Joined Sources | Number of Pruned Sources | 4396 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4397 | Joined Source Address 1 (Encoded-Source format) | 4398 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4399 | . | 4400 | . | 4401 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4402 | Joined Source Address n (Encoded-Source format) | 4403 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4404 | Pruned Source Address 1 (Encoded-Source format) | 4405 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4406 | . | 4407 | . | 4408 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4409 | Pruned Source Address n (Encoded-Source format) | 4410 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4412 PIM Version, Type, Reserved, Checksum 4413 Described above. 4415 Unicast Upstream Neighbor Address 4416 The address of the RPF or upstream neighbor. The format for this 4417 address is given in the Encoded-Unicast address in section 4.9.1. | 4418 This address should be the link-local address of the upstream | 4419 neighbor, as obtained from the RPF lookup. | 4421 Reserved 4422 Transmitted as zero, ignored on receipt. 4424 Holdtime 4425 The amount of time a receiver must keep the Join/Prune state alive, 4426 in seconds. If the Holdtime is set to `0xffff', the receiver of | 4427 this message should hold the state until canceled by the | 4428 appropriate cancelling Join/Prune message, or timed out according | 4429 to local policy. This may be used with dial-on-demand links, to | 4430 avoid keeping the link up with periodic Join/Prune messages. | 4432 Note that the HoldTime must be larger than the | 4433 J/P_Override_Interval. | 4435 Number of Groups 4436 The number of multicast group sets contained in the message. 4438 Multicast group address 4439 For format description see Section 4.9.1. 4441 Number of Joined Sources 4442 Number of join source addresses listed for a given group. 4444 Join Source Address 1 .. n 4445 This list contains the sources that the sending router will forward 4446 multicast datagrams for if received on the interface this message 4447 is sent on. 4449 See Encoded-Source-Address format in section 4.9.1. 4451 Number of Pruned Sources 4452 Number of prune source addresses listed for a group. 4454 Prune Source Address 1 .. n 4455 This list contains the sources that the sending router does not 4456 want to forward multicast datagrams for when received on the | 4457 interface this message is sent on. | 4459 4.9.5.1. Group Set Source List Rules | 4461 As described above, Join / Prune messages are composed by one or more | 4462 group sets. Each set contains two source lists, the Join Sources and the | 4463 Prune Sources. This section describes the different types of group sets | 4464 and source list entries that can exist in a Join / Prune message. | 4466 There are two valid group set types: | 4468 Wildcard Group Set | 4469 The wildcard group set is represented by the entire multicast range | 4470 - the beginning of the multicast address range in the group address | 4471 field and the prefix length of the multicast address range in the | 4472 mask length field of the Multicast Group Address, e.g. 224.0.0.0/4 | 4473 for IPv4. Each wildcard group set may contain one or more (*,*,RP) | 4474 source list entries in either the Join or Prune lists. | 4476 A (*,*,RP) source list entry may only exist in a wildcard group | 4477 set. When added to a Join source list, this type of source entry | 4478 expresses the routers interest in receiving traffic for all groups | 4479 mapping to the specified RP. When added to a Prune source list a | 4480 (*,*,RP) entry expresses the routers interest to stop receiving | 4481 such traffic. | 4483 (*,*,RP) source list entries have the Source-Address set to the | 4484 address of the RP, the Source-Address Mask-Len set to the full | 4485 length of the IP address and both the WC and RPT bits of the | 4486 Source-Address set to 1. | 4488 Group Specific Set | 4489 For IPv4, a Group Specific Set is represented by a valid IP | 4490 multicast address in the group address field and the full length of | 4491 the IP address in the mask length field of the Multicast Group | 4492 Address. Each group specific set may contain (*,G), (S,G,rpt) and | 4493 (S,G) source list entries in the Join or Prune lists. | 4495 (*,G) | 4496 The (*,G) source list entry is used in Join / Prune messages | 4497 sent towards the RP for the specified group. It expresses | 4498 interest (or lack of) in receiving traffic sent to the group | 4499 through the Rendezvous-Point shared tree. There may only be | 4500 one such entry in both the Join and Prune lists of a group | 4501 specific set. | 4503 (*,G) source list entries have the Source-Address set to the | 4504 address of the RP for group G, the Source-Address Mask-Len set | 4505 to the full length of the IP address and have both the WC and | 4506 RPT bits of the Encoded-Source-Address set. | 4508 (S,G,rpt) | 4509 The (S,G,rpt) source list entry is used in Join / Prune | 4510 messages sent towards the RP for the specified group. It | 4511 expresses interest (or lack of) in receiving traffic through | 4512 the shared tree sent by the specified source to this group. | 4513 There may only be one such entry for each source address in | 4514 both the Join and Prune lists of a group specific set. | 4516 (S,G,rpt) source list entries have the Source-Address set to | 4517 the address of the source S, the Source-Address Mask-Len set | 4518 to the full length of the IP address and have the WC bit clear | 4519 and the RPT bit set in the Encoded-Source-Address. | 4521 (S,G) | 4522 The (S,G) source list entry is used in Join / Prune messages | 4523 sent towards the specified source. It expresses interest (or | 4524 lack of) in receiving traffic through the shortest path tree | 4525 sent by the source to the specified group. There may only be | 4526 one such entry for each source address in both the Join and | 4527 Prune lists of a group specific set. | 4529 (S,G) source list entries have the Source-Address set to the | 4530 address of the source S, the Source-Address Mask-Len set to | 4531 the full length of the IP address and have both the WC and RPT | 4532 bits of the Encoded-Source-Address clear. | 4534 The rules described above are sufficient to prevent invalid combinations | 4535 of source list entries in group-specific sets. There are however a | 4536 number of combinations that have a valid interpretation but which are | 4537 not generated by the protocol as described in this specification: | 4539 o Combining a (*,G) Join and a (S,G,rpt) Join entry in the same message | 4540 is redundant as the (*,G) entry covers the information provided by the | 4541 (S,G,rpt) entry. | 4543 o The same applies for a (*,G) Prunes and (S,G,rpt) Prunes. | 4544 o The combination of a (*,G) Prune and a (S,G,rpt) Join is also not | 4545 generated. (S,G,rpt) Joins are only sent when the router is receiving | 4546 all traffic for a group on the shared tree and it wishes to indicate a | 4547 change for the particular source. As a (*,G) prune indicates that the | 4548 router no longer wishes to receive shared tree traffic, the (S,G,rpt) | 4549 Join is meaningless. | 4551 o As Join / Prune messages are targeted to a single PIM neighbour, | 4552 including both a (S,G) Join and a (S,G,rpt) prune in the same message | 4553 is redundant. The (S,G) Join informs the neighbour that the sender | 4554 wishes to receive the particular source on the shortest path tree. It | 4555 is therefore unnecessary for the router to say that it no longer | 4556 wishes to receive it on the shared tree. | 4558 o The combination of a (S,G) Prune and a (S,G,rpt) Join could possibly | 4559 be used by a router to switch from receiving a particular source on | 4560 the shortest-path tree back to receiving it on the shared tree | 4561 (provided that the RPF neighbor for the shortest-path and shared trees | 4562 is common). However Sparse-Mode PIM does not provide a mechanism for | 4563 switching back to the shared tree. | 4565 The rules are summarised in the table below. 4567 +-----------++-------+--------+------------+------------+--------+-------|| 4568 | ||(*,G)J | (*,G)P | (S,G,rpt)J | (S,G,rpt)P | (S,G)J | (S,G)P|| 4569 +-----------++-------+--------+------------+------------+--------+--------| 4570 |(*,G)J ||- | no | ? | yes | yes | yes || 4571 +-----------++-------+--------+------------+------------+--------+--------| 4572 |(*,G)P || | - | ? | ? | yes | yes || 4573 +-----------++-------+--------+------------+------------+--------+--------| 4574 |(S,G,rpt)J || | | - | no | yes | yes || 4575 +-----------++-------+--------+------------+------------+--------+--------| 4576 |(S,G,rpt)P || | | | - | ? | ? || 4577 +-----------++-------+--------+------------+------------+--------+--------| 4578 |(S,G)J || | | | | - | no || 4579 +-----------++-------+--------+------------+------------+--------+--------| 4580 |(S,G)P || | | | | | - || 4581 +-----------++-------+--------+------------+------------+--------+--------| 4583 yes Allowed and expected. | 4585 no Combination is not allowed by the protocol and MUST not be | 4586 generated by a router. | 4588 ? Combination not expected by the protocol, but well-defined. A | 4589 router MAY accept it but SHOULD not generate it. | 4591 The order of source list entries in a group set source list is not | 4592 important. As a result the table above is symmetric and only entries on | 4593 the upper right half have been specified as entries on the lower left | 4594 are just a mirror. | 4596 4.9.5.2. Group Set Fragmentation | 4598 When building a Join / Prune for a prticular neighbour, a router should | 4599 try and include in the message as much of the information it needs to | 4600 convey to the neighbour as possible. This implies adding one group set | 4601 for each multicast group that has information pending transmission and | 4602 within each set including all relevant source list entries. | 4604 On a router with a large amount of multicast state the number of entries | 4605 that must be included may result in packets that are larger in the | 4606 maximum IP packet size. In most such cases the information may be split | 4607 into multiple messages. | 4609 There is an exception with group sets that contain a (*,G) Join source | 4610 list entry. The group set expresses the routers interest in receiving | 4611 all traffic for the specified group on the shared tree and it MUST | 4612 include an (S,G,rpt) Prune source list entry for every source that the | 4613 router does not wish to receive. This list of (S,G,rpt) Prune source- | 4614 list entries MUST not be split in multiple messages. | 4616 If only N (S,G,rpt) Prune entries fit into a maximum-sized Join / Prune | 4617 message, but the router has more than N (S,G,rpt) Prunes to add, then | 4618 the router MUST choose to include the first N (numerically smallest) IP | 4619 addresses. | 4621 4.9.6. Assert Message Format 4623 The Assert message is sent when a multicast data packet is received on 4624 an outgoing interface corresponding to the (S,G) or (*,G) associated 4625 with the source. 4627 0 1 2 3 4628 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 4629 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4630 |PIM Ver| Type | Reserved | Checksum | 4631 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4632 | Group Address (Encoded-Group format) | 4633 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4634 | Source Address (Encoded-Unicast format) | 4635 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4636 |R| Metric Preference | 4637 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4638 | Metric | 4639 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4641 PIM Version, Type, Reserved, Checksum 4642 Described above. 4644 Group Address 4645 The group address to which the data packet was addressed, and which 4646 triggered the Assert. This is an Encoded-Group address, as 4647 specified in 4.9.1. 4649 Source Address 4650 Source address from multicast datagram that triggered the Assert 4651 packet to be sent. The format for this address is given in Encoded- 4652 Unicast-Address in section 4.9.1. 4654 R RPT-bit is a 1 bit value. If the multicast datagram that triggered 4655 the Assert packet is routed down the RP tree, then the RPT-bit is 4656 1; if the multicast datagram is routed down the SPT, it is 0. 4658 Metric Preference 4659 Preference value assigned to the unicast routing protocol that 4660 provided the route to Host address. 4662 Metric 4663 The unicast routing table metric. The metric is in units 4664 applicable to the unicast routing protocol used. 4666 4.10. PIM Timers 4668 PIM-SM maintains the following timers, as discussed in section 4.1. All 4669 timers are countdown timers - they are set to a value and count down to 4670 zero, at which point they typically trigger an action. Of course they 4671 can just as easily be implemented as count-up timers, where the absolute 4672 expiry time is stored and compared against a real-time clock, but the 4673 language in this specification assumes that they count downwards to 4674 zero. 4676 Global Timers 4678 Hello Timer: HT 4680 Per interface (I): 4682 Per neighbor (N): 4684 Neighbor liveness Timer: NLT(N,I) 4686 Per active RP (RP): 4688 (*,*,RP) Join Expiry Timer: ET(*,*,RP,I) 4690 (*,*,RP) PrunePending Timer: PPT(*,*,RP,I) 4692 Per Group (G): 4694 (*,G) Join Expiry Timer: ET(*,G,I) 4695 (*,G) PrunePending Timer: PPT(*,G,I) 4697 (*,G) Assert Timer: AT(*,G,I) 4699 Per Source (S): 4701 (S,G) Join Expiry Timer: ET(S,G,I) 4703 (S,G) PrunePending Timer: PPT(S,G,I) 4705 (S,G) Assert Timer: AT(S,G,I) 4707 (S,G,rpt) Prune Expiry Timer: ET(S,G,rpt,I) 4709 (S,G,rpt) PrunePending Timer: PPT(S,G,rpt,I) 4711 Per active RP (RP): 4713 (*,*,RP) Upstream Join Timer: JT(*,*,RP) 4715 Per Group (G): 4717 (*,G) Upstream Join Timer: JT(*,G) 4719 Per Source (S): 4721 (S,G) Upstream Join Timer: JT(S,G) 4723 (S,G) Keepalive Timer: KAT(S,G) 4725 (S,G,rpt) Upstream Override Timer: OT(S,G,rpt) 4727 At the DRs or relevant Assert Winners only: 4729 Per Source,Group pair (S,G): 4731 Register Stop Timer: RST(S,G) 4733 4.11. Timer Values 4735 When timers are started or restarted, they are set to default values. 4736 This section summarizes those default values. 4738 Timer Name: Hello Timer (HT) 4740 +----------------------+--------+---------------------------------------+| 4741 |Value Name | Value | Explanation | 4742 +----------------------+--------+---------------------------------------+ 4743 |Hello_Period | 30 sec | Periodic interval for hello messages. | 4744 +----------------------+--------+---------------------------------------+| 4745 |Triggered_Hello_Delay | 5 sec | Randomized interval for initial Hello || 4746 | | | message on bootup or triggered Hello || 4747 | | | message to a rebooting neighbor. || 4748 +----------------------+--------+---------------------------------------+| 4750 Hello messages are sent on every active interface once every 4751 Hello_Period seconds. At system power-up, the timer is initialized to | 4752 rand(0,Triggered_Hello_Delay) to prevent synchronization. When a new or | 4753 rebooting neighbor is detected, a responding Hello is sent within 4754 rand(0,Triggered_Hello_Delay). 4756 Timer Name: Neighbor Liveness Timer (NLT(N,I)) 4758 +-------------------+-----------------+---------------------------------+ 4759 | Value Name | Value | Explanation | 4760 +-------------------+-----------------+---------------------------------+ 4761 | Hello Holdtime | from message | Hold Time from Hello Message | 4762 +-------------------+-----------------+---------------------------------+ 4764 The Holdtime in a Hello Message should be set to (3.5 * Hello_Period), 4765 giving a default value of 105 seconds. 4767 Timer Names: Expiry Timer (ET(*,*,RP,I), ET(*,G,I), ET(S,G,I), 4768 ET(S,G,rpt,I)) 4770 +----------------+----------------+-------------------------------------+ 4771 | Value Name | Value | Explanation | 4772 +----------------+----------------+-------------------------------------+ 4773 | J/P HoldTime | from message | Hold Time from Join/Prune Message | 4774 +----------------+----------------+-------------------------------------+ 4776 See details of JT(*,G) for the Hold Time that is included in Join/Prune 4777 Messages. 4779 Timer Names: Prune Pending Timer (PPT(*,*,RP,I), PPT(*,G,I), PPT(S,G,I), 4780 PPT(S,G,rpt,I)) 4782 +--------------------------+--------------------+-----------------------+ 4783 | Value Name | Value | Explanation | 4784 +--------------------------+--------------------+-----------------------+ 4785 | J/P Override Interval | Default: 3 secs | Short period after | 4786 | | | a join or prune to | 4787 | | | allow other | 4788 | | | routers on the LAN | 4789 | | | to override the | 4790 | | | join or prune | 4791 +--------------------------+--------------------+-----------------------+ 4793 Timer Names: Assert Timer (AT(*,G,I), AT(S,G,I)) 4795 +---------------------------+----------------------+--------------------+ 4796 | Value Name | Value | Explanation | 4797 +---------------------------+----------------------+--------------------+ 4798 | Assert Override Interval | Default: 3 secs | Short interval | 4799 | | | before an assert | 4800 | | | times out where | 4801 | | | the assert winner | 4802 | | | resends an assert | 4803 | | | message | 4804 +---------------------------+----------------------+--------------------+ 4805 | Assert Time | Default: 180 secs | Period after last | 4806 | | | assert before | 4807 | | | assert state is | 4808 | | | timed out | 4809 +---------------------------+----------------------+--------------------+ 4811 Note that for historical reasons, the Assert message lacks a Holdtime 4812 field. Thus changing the Assert Time from the default value is not 4813 recommended. 4815 Timer Names: Upstream Join Timer (JT(*,*,RP), JT(*,G), JT(S,G)) 4817 +-------------+--------------------+------------------------------------+ 4818 |Value Name |Value |Explanation | 4819 +-------------+--------------------+------------------------------------+ 4820 |t_periodic |Default: 60 secs |Period between Join/Prune Messages | 4821 +-------------+--------------------+------------------------------------+ 4822 |t_suppressed |rand(1.1 * |Suppression period when someone | 4823 | |t_periodic, 1.4 * |else sends a J/P message so we | 4824 | |t_periodic) |don't need to do so. | 4825 +-------------+--------------------+------------------------------------+ 4826 |t_override |rand(0, 0.9 * J/P |Randomized delay to prevent | 4827 | |Override Interval) |response implosion when sending a | 4828 | | |join message to override someone | 4829 | | |else's prune message. | 4830 +-------------+--------------------+------------------------------------+ 4832 t_periodic may be set to take into account such things as the configured 4833 bandwidth and expected average number of multicast route entries for the 4834 attached network or link (e.g., the period would be longer for lower- 4835 speed links, or for routers in the center of the network that expect to 4836 have a larger number of entries). If the Join/Prune-Period is modified 4837 during operation, these changes should be made relatively infrequently 4838 and the router should continue to refresh at its previous Join/Prune- 4839 Period for at least Join/Prune-Holdtime, in order to allow the upstream 4840 router to adapt. 4842 0.9 * J/P Override Interval is really an attempt to estimate the true 4843 desired max value of t_override, which is the J/P Override Interval 4844 minus the local network's propagation delay. If the network's 4845 propagation delay is actually known, the value (J/P Override Interval - 4846 propagation delay) may be used instead. 4848 The holdtime specified in a Join/Prune message should be set to (3.5 * 4849 t_periodic). 4851 Timer Name: KeepAlive Timer (KAT(S,G)) 4853 +-----------------------+------------------------+----------------------+ 4854 | Value Name | Value | Explanation | 4855 +-----------------------+------------------------+----------------------+ 4856 | Keepalive_Period | Default: 210 secs | Period after last | 4857 | | | (S,G) data packet | 4858 | | | during which (S,G) | 4859 | | | Join state will be | 4860 | | | maintained even in | 4861 | | | the absence of | 4862 | | | (S,G) Join | 4863 | | | messages. | 4864 +-----------------------+------------------------+----------------------+ 4865 | RP_Keepalive_Period | ( 3 * Register | As | 4866 | | Period Suppression | Keepalive_Period, | 4867 | | ) + Register Probe | but at the RP when | 4868 | | Time | a RegisterStop is | 4869 | | | sent. | 4870 +-----------------------+------------------------+----------------------+ 4871 The normal keepalive period for the KAT(S,G) defaults to 210 seconds. 4872 However at the RP, the keepalive period must be at least the 4873 Register_Suppression_Time or the RP may time out the (S,G) state before 4874 the next Null-Register arrives. Thus the KAT(S,G) is set to 4875 max(Keepalive_Period, RP_Keepalive_Period). 4877 Timer Name: Upstream Override Timer (OT(S,G,rpt)) 4879 +------------------+--------------------------+-------------------------+ 4880 | Value Name | Value | Explanation | 4881 +------------------+--------------------------+-------------------------+ 4882 | t_po | rand(0, 0.9 * | Randomized delay | 4883 | | Join/Prune | to prevent | 4884 | | Override Interval) | response implosion | 4885 | | | when sending a | 4886 | | | join message to | 4887 | | | override someone | 4888 | | | else's prune | 4889 | | | message. | 4890 +------------------+--------------------------+-------------------------+ 4892 As with t_override, the network's propagation delay may be used if 4893 known. XXX t_po and t_override seem to be the same thing??? 4894 Timer Name: Register Stop Timer (RST(S,G)) 4896 +---------------------------+----------------------+--------------------+ 4897 |Value Name |Value | Explanation | 4898 +---------------------------+----------------------+--------------------+ 4899 |Register Suppression Time |Default: 60 seconds | Period during | 4900 | | | which a DR stops | 4901 | | | sending Register- | 4902 | | | encapsulated data | 4903 | | | to the RP after | 4904 | | | receiving a | 4905 | | | RegisterStop | 4906 +---------------------------+----------------------+--------------------+ 4907 |Register Probe Time |Default: 5 seconds | Time before RST | 4908 | | | expires when a DR | 4909 | | | may send a Null- | 4910 | | | Register to the RP | 4911 | | | to cause it to | 4912 | | | resend a | 4913 | | | RegisterStop | 4914 | | | message. | 4915 +---------------------------+----------------------+--------------------+ 4917 5. IANA Considerations 4919 5.1. PIM Address Family 4921 The PIM Address Family field was chosen to be 8 bits as a tradeoff 4922 between 4923 packet format and use of the IANA assigned numbers. Since when the PIM 4924 packet format was designed only 15 values were assigned for Address 4925 Families, and large numbers of new Address Family values were not 4926 envisioned, 8 bits seemed large enough. However, the IANA assigns 4927 Address Families in a 16-bit field. Therefore, the PIM Address Family 4928 is allocated as follows: 4930 Values 0 through 127 are designated to have the same meaning as 4931 IANA-assigned Address Family Numbers [5]. 4933 Values 128 through 250 are designated to be assigned by the IANA 4934 based upon IESG Approval, as defined in [6]. XXX note: is the IESG 4935 OK with this? 4937 Values 251 through 255 are designated for Private Use, as defined 4938 in [6]. 4940 5.2. PIM Hello Options 4942 Values 17 through 65000 are to be assigned by the IANA. Since the space 4943 is large, they may be assigned as First Come First Served as defined in 4944 [6]. Such assignments are valid for one year, and may be renewed. 4945 Permanent assignments require a specification (see "Specification 4946 Required" in [6].) 4948 6. Security Considerations 4950 All PIM control messages MAY use IPsec [7] to address security concerns. 4951 The authentication methods are addressed in a companion document [9]. 4952 Keys may be distributed as described in [10]. 4954 XXX This probably needs more. 4956 7. Authors' Addresses 4958 Bill Fenner 4959 AT&T Labs - Research 4960 75 Willow Road 4961 Menlo Park, CA 94025 4962 fenner@research.att.com 4964 Mark Handley 4965 ACIRI/ICSI 4966 1947 Center St, Suite 600 4967 Berkeley, CA 94708 4968 mjh@aciri.org 4970 Hugh Holbrook 4971 Cisco Systems 4972 170 W. Tasman Drive 4973 San Jose, CA 95134 4974 holbrook@cisco.com 4976 Isidor Kouvelas 4977 Cisco Systems 4978 170 W. Tasman Drive 4979 San Jose, CA 95134 4980 kouvelas@cisco.com 4982 8. Acknowledgments 4984 PIM-SM was designed over many years by a large group of people, 4985 including ideas from Deborah Estrin, Dino Farinacci, Ahmed Helmy, David 4986 Thaler, Steve Deering, Van Jacobson, C. Liu, Puneet Sharma, Liming Wei, 4987 Tom Pusateri, Tony Ballardie, Scott Brim, Jon Crowcroft, Paul Francis, 4988 Joel Halpern, Horst Hodel, Polly Huang, Stephen Ostrowski, Lixia Zhang, | 4989 Girish Chandranmenon, Brian Haberman, Hal Sandick, and Garry Kump. | 4991 Thanks are due to the American Licorice Company, for its obscure but 4992 possibly essential role in the creation of this document. 4994 This specification has been blessed by St. Isidor. 4996 9. References 4998 [1] T. Bates , R. Chandra , D. Katz , Y. Rekhter, "Multiprotocol 4999 Extensions for BGP-4", RFC 2283 5001 [2] S.E. Deering, "Host extensions for IP multicasting", RFC 1112, Aug 5002 1989. 5004 [3] W. Fenner, "Internet Group Management Protocol, Version 2", RFC 5005 2236. 5007 [4] W. Fenner, M. Handley, H. Holbrook, I. Kouvelas, "Bootstrap Router | 5008 (BSR) Mechanism for PIM Sparse Mode", draft-ietf-pim-sm-bsr-00.txt, | 5009 work in progress. | 5011 [5] IANA, "Address Family Numbers", linked from | 5012 http://www.iana.org/numbers.html 5014 [6] T. Narten , H. Alvestrand, "Guidelines for Writing an IANA 5015 Considerations Section in RFCs", RFC 2434. 5017 [7] S. Kent, R. Atkinson, "Security Architecture for the Internet 5018 Protocol.", RFC 2401. 5020 [8] S. Deering, R. Hinden, "Internet Protocol, Version 6 (IPv6) 5021 Specification", RFC 2460. 5023 [9] L. Wei, "Authenticating PIM version 2 messages", draft-ietf-pim- 5024 v2-auth-01.txt, work in progress. 5026 [10] T. Hardjono, B. Cain, "Simple Key Management Protocol for PIM", 5027 draft-ietf-pim-simplekmp-01.txt, work in progress. 5029 [11] H. Holbrook, B. Cain, "Source-Specific Multicast for IP", draft- 5030 holbrook-ssm-00.txt, work in progress. 5032 10. Index 5033 AssertCancel(*,G). . . . . . . . . . . . . . . . . . . . . . . . . . 80 5034 AssertTimer(*,G,I) . . . . . . . . . . . . . . . . . . . . .15,22,74,112 5035 AssertTimer(S,G,I) . . . . . . . . . . . . . . . . . . . . .16,22,68,112 5036 AssertTrackingDesired(*,G,I) . . . . . . . . . . . . . . . . . . . . 77 5037 AssertTrackingDesired(S,G,I) . . . . . . . . . . . . . . . . . . . . 70 5038 AssertWinner(*,G,I). . . . . . . . . . . . . . . . . . . . . . . . 20,22 5039 AssertWinner(S,G,I). . . . . . . . . . . . . . . . . . . . . . .20,22,82 5040 assert_metric. . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 5041 Assert_Override_Interval . . . . . . . . . . . . . . . . . . . 73,80,112 5042 Assert_Time. . . . . . . . . . . . . . . . . . . . . . . . . . 73,80,112 5043 AT(*,G,I). . . . . . . . . . . . . . . . . . . . . . . . . .15,22,74,112 5044 AT(S,G,I). . . . . . . . . . . . . . . . . . . . . . . . . .16,22,68,112 5045 CouldAssert(*,G,I) . . . . . . . . . . . . . . . . . . . . . . . . . 77 5046 CouldAssert(S,G,I) . . . . . . . . . . . . . . . . . . . . . . . . 70,70 5047 CouldRegister(S,G) . . . . . . . . . . . . . . . . . . . . . . . . . 29 5048 DirectlyConnected(S) . . . . . . . . . . . . . . . . . . . . . .24,25,29 5049 DownstreamJPState(*,*,RP,I). . . . . . . . . . . . . . . . . . . . . 20 5050 DownstreamJPState(*,G,I) . . . . . . . . . . . . . . . . . . . . . . 21 5051 DownstreamJPState(S,G,I) . . . . . . . . . . . . . . . . . . . . . . 21 5052 DR(I). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 5053 dr_is_better(a,b,I). . . . . . . . . . . . . . . . . . . . . . . . . 87 5054 ET(*,*,RP,I) . . . . . . . . . . . . . . . . . . . . . . . . . 14,32,111 5055 ET(*,G,I). . . . . . . . . . . . . . . . . . . . . . . . . . . 15,36,111 5056 ET(S,G,I). . . . . . . . . . . . . . . . . . . . . . . . . . . 16,40,111 5057 ET(S,G,rpt,I). . . . . . . . . . . . . . . . . . . . . . . . . 18,44,111 5058 Hash_Function. . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 5059 Hello_Holdtime . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 5060 Hello_Period . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 5061 HT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 5062 immediate_olist(*,*,RP). . . . . . . . . . . . . . . . . . . . . . 19,51 5063 immediate_olist(*,G) . . . . . . . . . . . . . . . . . . . . . . . 19,54 5064 immediate_olist(S,G) . . . . . . . . . . . . . . . . . . . . . .19,59,81 5065 infinite_assert_metric() . . . . . . . . . . . . . . . . . . . . . . 82 5066 inherited_olist(S,G) . . . . . . . . . . . . . . . . . . .20,24,30,59,70 5067 inherited_olist(S,G,rpt) . . . . . . . . . . . . . .20,24,25,63,65,67,81 5068 I_am_DR(I) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20,29 5069 I_am_RP(G) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 5070 J/P_HoldTime . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 5071 J/P_Override_Interval. . . . . . . . . . . . . . . . . . 34,38,42,46,112 5072 Join(*,G). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 5073 join(S,G). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 5074 JoinDesired(*,*,RP). . . . . . . . . . . . . . . . . . . . . . . . 51,64 5075 JoinDesired(*,G) . . . . . . . . . . . . . . . . . . . . . . . . . 54,64 5076 JoinDesired(S,G) . . . . . . . . . . . . . . . . . . . . . . . .25,59,70 5077 joins(*,*,RP). . . . . . . . . . . . . . . . . . . . . . . . . . . 20,77 5078 joins(*,G) . . . . . . . . . . . . . . . . . . . . . . . . . . .21,70,77 5079 joins(S,G) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 5080 JT(*,*,RP) . . . . . . . . . . . . . . . . . . . . . . . . . . 14,49,113 5081 JT(*,G). . . . . . . . . . . . . . . . . . . . . . . . . . . . 15,53,113 5082 JT(S,G). . . . . . . . . . . . . . . . . . . . . . . . . . . . 17,58,113 5083 KAT(S,G) . . . . . . . . . . . . . . . . . . . . . . .17,24,29,30,59,113 5084 KeepaliveTimer(S,G). . . . . . . . . . . . . . . . . .17,24,29,30,59,113 5085 Keepalive_Period . . . . . . . . . . . . . . . . . . . . . . . . . . 113 5086 local_receiver_exclude(S,G,I). . . . . . . . . . . . . . . . . . . . 20 5087 local_receiver_include(*,G,I). . . . . . . . . . . . . . . . . . . . 20 5088 local_receiver_include(S,G,I). . . . . . . . . . . . . . . . . . . . 20 5089 lost_assert(*,G) . . . . . . . . . . . . . . . . . . . . . . . . . . 21 5090 lost_assert(*,G,I) . . . . . . . . . . . . . . . . . . . . . 20,21,70,83 5091 lost_assert(S,G) . . . . . . . . . . . . . . . . . . . . . . . . . . 22 5092 lost_assert(S,G,I) . . . . . . . . . . . . . . . . . . . . . . .20,22,83 5093 lost_assert(S,G,rpt) . . . . . . . . . . . . . . . . . . . . . . . . 22 5094 lost_assert(S,G,rpt,I) . . . . . . . . . . . . . . . . . . . . . . 22,82 5095 MBGP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 5096 MRIB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 5097 MRIB.next_hop(host). . . . . . . . . . . . . . . . . . . . . . . . . 22 5098 my_assert_metric(S,G,I). . . . . . . . . . . . . . . . . . . . . . . 81 5099 NLT(N,I) . . . . . . . . . . . . . . . . . . . . . . . . . . . . .13,111 5100 OT(S,G,rpt). . . . . . . . . . . . . . . . . . . . . . . . . . . .18,114 5101 packet_arrives_on_rp_tunnel(pkt) . . . . . . . . . . . . . . . . . . 30 5102 pim_exclude(S,G) . . . . . . . . . . . . . . . . . . . . . . . . . . 20 5103 pim_exclude(S,G,I) . . . . . . . . . . . . . . . . . . . . . . . . . 70 5104 pim_include(*,G) . . . . . . . . . . . . . . . . . . . . . . . . . 20,77 5105 pim_include(*,G,I) . . . . . . . . . . . . . . . . . . . . . . . . . 70 5106 pim_include(S,G) . . . . . . . . . . . . . . . . . . . . . . . . . 20,70 5107 PPT(*,*,RP,I). . . . . . . . . . . . . . . . . . . . . . . . . 14,32,112 5108 PPT(*,G,I) . . . . . . . . . . . . . . . . . . . . . . . . . . 15,36,112 5109 PPT(S,G,I) . . . . . . . . . . . . . . . . . . . . . . . . . . 16,40,112 5110 PPT(S,G,rpt,I) . . . . . . . . . . . . . . . . . . . . . . . . 18,44,112 5111 PruneDesired(S,G,rpt). . . . . . . . . . . . . . . . . . . . . . . 65,66 5112 prunes(S,G,rpt). . . . . . . . . . . . . . . . . . . . . . . . . . 21,70 5113 RegisterStop . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 5114 RegisterStop(*,G). . . . . . . . . . . . . . . . . . . . . . . . . . 29 5115 RegisterStop(S,G). . . . . . . . . . . . . . . . . . . . . . . . . . 30 5116 RegisterStop_timer . . . . . . . . . . . . . . . . . . . . . . . . . 27 5117 Register_Probe_Time. . . . . . . . . . . . . . . . . . . . . . 28,31,115 5118 Register_Suppression_Time. . . . . . . . . . . . . . . . . 28,31,114,115 5119 RP(G). . . . . . . . . . . . . . . . . . . . . . . . . . . . . .22,77,77 5120 RPF'(*,G). . . . . . . . . . . . . . . . . . . . . . . . . . . .22,25,63 5121 RPF'(S,G). . . . . . . . . . . . . . . . . . . . . . . . . . . .22,25,63 5122 RPF'(S,G,rpt). . . . . . . . . . . . . . . . . . . . . . . . . .22,63,65 5123 RPF_interface. . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 5124 RPF_interface(host). . . . . . . . . . . . . . . . .22,24,25,29,70,77,82 5125 RPTJoinDesired(G). . . . . . . . . . . . . . . . . . . . . . . .64,67,77 5126 rpt_assert_metric(G,I) . . . . . . . . . . . . . . . . . . . . . . . 81 5127 RST(S,G) . . . . . . . . . . . . . . . . . . . . . . . . . . . . .27,115 5128 SPTbit(S,G). . . . . . . . . . . . . . . . . . . . . . . .24,25,30,63,81 5129 spt_assert_metric(S,I) . . . . . . . . . . . . . . . . . . . . . . . 81 5130 SSM. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 5131 Triggered_Hello_Delay. . . . . . . . . . . . . . . . . . . . . . . . 111 5132 t_override . . . . . . . . . . . . . . . . . . . . . . . . . . 50,54,113 5133 t_periodic . . . . . . . . . . . . . . . . . . . . . . . . . . 50,54,113 5134 t_po . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .64,114 5135 t_suppressed . . . . . . . . . . . . . . . . . . . . . . . . . 50,54,113 5136 Update_SPTbit(S,G,iif) . . . . . . . . . . . . . . . . . . . . . . . 25 5137 UpstreamJPState(S,G) . . . . . . . . . . . . . . . . . . . . . . . . 24