idnits 2.17.1 draft-ietf-pim-sm-v2-new-11.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** It looks like you're using RFC 3978 boilerplate. You should update this to the boilerplate described in the IETF Trust License Policy document (see https://trustee.ietf.org/license-info), which is required now. -- Found old boilerplate from RFC 3667, Section 5.1 on line 17. -- Found old boilerplate from RFC 3978, Section 5.5 on line 6576. -- Found old boilerplate from RFC 3979, Section 5, paragraph 1 on line 6549. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 6556. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 6562. ** The document seems to lack an RFC 3978 Section 5.1 IPR Disclosure Acknowledgement -- however, there's a paragraph with a matching beginning. Boilerplate error? ** This document has an original RFC 3978 Section 5.4 Copyright Line, instead of the newer IETF Trust Copyright according to RFC 4748. ** This document has an original RFC 3978 Section 5.5 Disclaimer, instead of the newer disclaimer which includes the IETF Trust according to RFC 4748. ** The document uses RFC 3667 boilerplate or RFC 3978-like boilerplate instead of verbatim RFC 3978 boilerplate. After 6 May 2005, submission of drafts without verbatim RFC 3978 boilerplate is not accepted. The following non-3978 patterns matched text found in the document. That text should be removed or replaced: By submitting this Internet-Draft, I certify that any applicable patent or other IPR claims of which I am aware have been disclosed, or will be disclosed, and any of which I become aware will be disclosed, in accordance with RFC 3668. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- == No 'Intended status' indicated for this document; assuming Proposed Standard == The page length should not exceed 58 lines per page, but there was 18 longer pages, the longest (page 67) being 67 lines Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** There are 580 instances of too long lines in the document, the longest one being 11 characters in excess of 72. == There are 2 instances of lines with multicast IPv4 addresses in the document. If these are generic example addresses, they should be changed to use the 233.252.0.x range defined in RFC 5771 == There are 1 instance of lines with non-RFC3849-compliant IPv6 addresses in the document. If these are example addresses, they should be changed. ** The document seems to lack a both a reference to RFC 2119 and the recommended RFC 2119 boilerplate, even if it appears to use RFC 2119 keywords. RFC 2119 keyword, line 1314: '...Hello messages MUST be sent on all act...' RFC 2119 keyword, line 1320: '...liant PIM router MUST send Hello messa...' RFC 2119 keyword, line 1336: '...address, then it MUST immediately send...' RFC 2119 keyword, line 1342: '...ity. The DR_Priority Option SHOULD be...' RFC 2119 keyword, line 1349: '...r (GenID) Option SHOULD be included in...' (73 more instances...) Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the RFC 3978 Section 5.4 Copyright Line does not match the current year == Using lowercase 'not' together with uppercase 'MUST', 'SHALL', 'SHOULD', or 'RECOMMENDED' is not an accepted usage according to RFC 2119. Please use uppercase 'NOT' together with RFC 2119 keywords (if that is what you mean). Found 'MUST not' in this paragraph: There is an exception with group sets that contain a (*,G) Join source list entry. The group set expresses the router's interest in receiving all traffic for the specified group on the shared tree and it MUST include an (S,G,rpt) Prune source list entry for every source that the router does not wish to receive. This list of (S,G,rpt) Prune source-list entries MUST not be split in multiple messages. -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (25 October 2004) is 7094 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 4070 -- Looks like a reference, but probably isn't: 'Actions A6' on line 3713 -- Looks like a reference, but probably isn't: 'Actions A3' on line 4084 -- Looks like a reference, but probably isn't: 'Actions A2' on line 4098 -- Looks like a reference, but probably isn't: 'Actions A4' on line 4084 -- Looks like a reference, but probably isn't: 'Actions A5' on line 4112 ** Obsolete normative reference: RFC 2460 (ref. '4') (Obsoleted by RFC 8200) == Outdated reference: A later version (-07) exists of draft-ietf-ssm-arch-04 -- Possible downref: Non-RFC (?) normative reference: ref. '6' ** Obsolete normative reference: RFC 2401 (ref. '7') (Obsoleted by RFC 4301) ** Obsolete normative reference: RFC 2434 (ref. '8') (Obsoleted by RFC 5226) -- Obsolete informational reference (is this intentional?): RFC 2283 (ref. '9') (Obsoleted by RFC 2858) == Outdated reference: A later version (-12) exists of draft-ietf-pim-sm-bsr-03 == Outdated reference: A later version (-09) exists of draft-ietf-pim-bidir-05 -- Obsolete informational reference (is this intentional?): RFC 2409 (ref. '13') (Obsoleted by RFC 4306) == Outdated reference: A later version (-10) exists of draft-ietf-ipsec-esp-v3-06 == Outdated reference: A later version (-07) exists of draft-ietf-mboned-embeddedrp-04 Summary: 10 errors (**), 0 flaws (~~), 11 warnings (==), 17 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-11.txt Mark Handley/UCL 4 Hugh Holbrook/Cisco 5 Isidor Kouvelas/Cisco 6 25 October 2004 7 Expires: April 2005 9 Protocol Independent Multicast - Sparse Mode (PIM-SM): 10 Protocol Specification (Revised) 12 Status of this Document 14 By submitting this Internet-Draft, I certify that any applicable patent 15 or other IPR claims of which I am aware have been disclosed, or will be 16 disclosed, and any of which I become aware will be disclosed, in 17 accordance with RFC 3668. 19 Internet-Drafts are working documents of the Internet Engineering Task 20 Force (IETF), its areas, and its working groups. Note that other groups 21 may also distribute working documents as Internet-Drafts. 23 Internet-Drafts are draft documents valid for a maximum of six months 24 and may be updated, replaced, or obsoleted by other documents at any 25 time. It is inappropriate to use Internet-Drafts as reference material 26 or to cite them other than as "work in progress." 28 The list of current Internet-Drafts can be accessed at 29 http://www.ietf.org/ietf/1id-abstracts.txt 31 The list of Internet-Draft Shadow Directories can be accessed at 32 http://www.ietf.org/shadow.html. 34 This document is a product of the IETF PIM WG. Comments should be 35 addressed to the authors, or the mailing list at pim@ietf.org. 37 Abstract 39 This document specifies Protocol Independent Multicast - 40 Sparse Mode (PIM-SM). PIM-SM is a multicast routing protocol 41 that can use the underlying unicast routing information base 42 or a separate multicast-capable routing information base. It 43 builds unidirectional shared trees rooted at a Rendezvous 44 Point (RP) per group, and optionally creates shortest-path 45 trees per source. 47 Table of Contents 49 1. Introduction. . . . . . . . . . . . . . . . . . . . . . 6 50 2. Terminology . . . . . . . . . . . . . . . . . . . . . . 6 51 2.1. Definitions. . . . . . . . . . . . . . . . . . . . . 6 52 2.2. Pseudocode Notation. . . . . . . . . . . . . . . . . 7 53 3. PIM-SM Protocol Overview. . . . . . . . . . . . . . . . 8 54 4. Protocol Specification. . . . . . . . . . . . . . . . . 13 55 4.1. PIM Protocol State . . . . . . . . . . . . . . . . . 13 56 4.1.1. General Purpose State . . . . . . . . . . . . . . 14 57 4.1.2. (*,*,RP) State. . . . . . . . . . . . . . . . . . 15 58 4.1.3. (*,G) State . . . . . . . . . . . . . . . . . . . 16 59 4.1.4. (S,G) State . . . . . . . . . . . . . . . . . . . 18 60 4.1.5. (S,G,rpt) State . . . . . . . . . . . . . . . . . 20 61 4.1.6. State Summarization Macros. . . . . . . . . . . . 21 62 4.2. Data Packet Forwarding Rules . . . . . . . . . . . . 26 63 4.2.1. Last-hop Switchover to the SPT. . . . . . . . . . 28 64 4.2.2. Setting and Clearing the (S,G) SPTbit . . . . . . 29 65 4.3. Designated Routers (DR) and Hello Messages . . . . . 30 66 4.3.1. Sending Hello Messages. . . . . . . . . . . . . . 30 67 4.3.2. DR Election . . . . . . . . . . . . . . . . . . . 32 68 4.3.3. Reducing Prune Propagation Delay on LANs. . . . . 34 69 4.3.4. Maintaining Secondary Address Lists . . . . . . . 37 70 4.4. PIM Register Messages. . . . . . . . . . . . . . . . 38 71 4.4.1. Sending Register Messages from the DR . . . . . . 38 72 4.4.2. Receiving Register Messages at the RP . . . . . . 42 73 4.5. PIM Join/Prune Messages. . . . . . . . . . . . . . . 44 74 4.5.1. Receiving (*,*,RP) Join/Prune Messages. . . . . . 45 75 4.5.2. Receiving (*,G) Join/Prune Messages . . . . . . . 49 76 4.5.3. Receiving (S,G) Join/Prune Messages . . . . . . . 52 77 4.5.4. Receiving (S,G,rpt) Join/Prune Messages . . . . . 55 78 4.5.5. Sending (*,*,RP) Join/Prune Messages. . . . . . . 61 79 4.5.6. Sending (*,G) Join/Prune Messages . . . . . . . . 65 80 4.5.7. Sending (S,G) Join/Prune Messages . . . . . . . . 70 81 4.5.8. (S,G,rpt) Periodic Messages . . . . . . . . . . . 75 82 4.5.9. State Machine for (S,G,rpt) Triggered 83 Messages. . . . . . . . . . . . . . . . . . . . . 76 84 4.5.10. Background: (*,*,RP) and (S,G,rpt) 85 Interaction. . . . . . . . . . . . . . . . . . . 80 86 4.6. PIM Assert Messages. . . . . . . . . . . . . . . . . 82 87 4.6.1. (S,G) Assert Message State Machine. . . . . . . . 82 88 4.6.2. (*,G) Assert Message State Machine. . . . . . . . 90 89 4.6.3. Assert Metrics. . . . . . . . . . . . . . . . . . 97 90 4.6.4. AssertCancel Messages . . . . . . . . . . . . . . 98 91 4.6.5. Assert State Macros . . . . . . . . . . . . . . . 99 92 4.7. PIM Bootstrap and RP Discovery . . . . . . . . . . . 102 93 4.7.1. Group-to-RP Mapping . . . . . . . . . . . . . . . 103 94 4.7.2. Hash Function . . . . . . . . . . . . . . . . . . 104 95 4.8. Source-Specific Multicast. . . . . . . . . . . . . . 105 96 4.8.1. Protocol Modifications for SSM destination 97 addresses . . . . . . . . . . . . . . . . . . . . 105 98 4.8.2. PIM-SSM-only Routers. . . . . . . . . . . . . . . 106 99 4.9. PIM Packet Formats . . . . . . . . . . . . . . . . . 107 100 4.9.1. Encoded Source and Group Address Formats. . . . . 109 101 4.9.2. Hello Message Format. . . . . . . . . . . . . . . 112 102 4.9.3. Register Message Format . . . . . . . . . . . . . 115 103 4.9.4. Register-Stop Message Format. . . . . . . . . . . 117 104 4.9.5. Join/Prune Message Format . . . . . . . . . . . . 118 105 4.9.5.1. Group Set Source List Rules. . . . . . . . . . 121 106 4.9.5.2. Group Set Fragmentation. . . . . . . . . . . . 125 107 4.9.6. Assert Message Format . . . . . . . . . . . . . . 125 108 4.10. PIM Timers. . . . . . . . . . . . . . . . . . . . . 127 109 4.11. Timer Values. . . . . . . . . . . . . . . . . . . . 128 110 5. IANA Considerations . . . . . . . . . . . . . . . . . . 134 111 5.1. PIM Address Family . . . . . . . . . . . . . . . . . 134 112 5.2. PIM Hello Options. . . . . . . . . . . . . . . . . . 135 113 6. Security Considerations . . . . . . . . . . . . . . . . 135 114 6.1. Attacks based on forged messages . . . . . . . . . . 135 115 6.1.1. Forged link-local messages. . . . . . . . . . . . 135 116 6.1.2. Forged unicast messages . . . . . . . . . . . . . 136 117 6.2. Non-cryptographic Authentication Mechanisms. . . . . 136 118 6.3. Authentication using IPsec . . . . . . . . . . . . . 137 119 6.3.1. Protecting link-local multicast messages. . . . . 137 120 6.3.2. Protecting unicast messages . . . . . . . . . . . 138 121 6.3.2.1. Register messages. . . . . . . . . . . . . . . 138 122 6.3.2.2. Register-Stop messages . . . . . . . . . . . . 138 123 6.4. Denial of Service Attacks. . . . . . . . . . . . . . 139 124 7. Authors' Addresses. . . . . . . . . . . . . . . . . . . 139 125 8. Acknowledgments . . . . . . . . . . . . . . . . . . . . 140 126 9. Normative References. . . . . . . . . . . . . . . . . . 140 127 10. Informative References . . . . . . . . . . . . . . . . 141 128 11. Appendix A: PIM Multicast Border Router 129 Behavior . . . . . . . . . . . . . . . . . . . . . . . 142 130 11.1. Sources External to the PIM-SM Domain . . . . . . . 142 131 11.2. Sources Internal to the PIM-SM Domain . . . . . . . 143 132 12. Index. . . . . . . . . . . . . . . . . . . . . . . . . 145 133 13. Full Copyright Statement . . . . . . . . . . . . . . . 148 134 List of Figures 136 Figure 1. Per-(S,G) register state machine at a DR . . . . 38 137 Figure 2. Downstream per-interface (*,*,RP) state 138 machine. . . . . . . . . . . . . . . . . . . . . 46 139 Figure 3. Downstream per-interface (*,G) state 140 machine. . . . . . . . . . . . . . . . . . . . . 49 141 Figure 4. Downstream per-interface (S,G) state 142 machine. . . . . . . . . . . . . . . . . . . . . 53 143 Figure 5. Downstream per-interface (S,G,rpt) state 144 machine. . . . . . . . . . . . . . . . . . . . . 56 145 Figure 6. Upstream (*,*,RP) state machine. . . . . . . . . 61 146 Figure 7. Upstream (*,G) state machine . . . . . . . . . . 66 147 Figure 8. Upstream (S,G) state machine . . . . . . . . . . 71 148 Figure 9. Upstream (S,G,rpt) state machine for 149 triggered messages . . . . . . . . . . . . . . . 76 150 Figure 10. Per-interface (S,G) Assert State 151 machine . . . . . . . . . . . . . . . . . . . . 83 152 Figure 11. Per-interface (*,G) Assert State 153 machine . . . . . . . . . . . . . . . . . . . . 91 155 1. Introduction 157 This document specifies a protocol for efficiently routing multicast 158 groups that may span wide-area (and inter-domain) internets. This 159 protocol is called Protocol Independent Multicast - Sparse Mode (PIM-SM) 160 because, although it may use the underlying unicast routing to provide 161 reverse-path information for multicast tree building, it is not 162 dependent on any particular unicast routing protocol. 164 PIM-SM version 2 was originally specified in RFC 2117, and revised in 165 RFC 2362. This document is intended to obsolete RFC 2362, and to 166 correct a number of deficiencies that have been identified with the way 167 PIM-SM was previously specified. As far as possible, this document 168 specifies the same protocol as RFC 2362, and only diverges from the 169 behavior intended by RFC 2362 when the previously specified behavior was 170 clearly incorrect. Routers implemented according to the specification 171 in this document will be able to successfully interoperate with routers 172 implemented according to RFC 2362. 174 2. Terminology 176 In this document, the key words "MUST", "MUST NOT", "REQUIRED", "SHALL", 177 "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and 178 "OPTIONAL" are to be interpreted as described in RFC 2119 and indicate 179 requirement levels for compliant PIM-SM implementations. 181 2.1. Definitions 183 This specification uses a number of terms to refer to the roles of 184 routers participating in PIM-SM. The following terms have special 185 significance for PIM-SM: 187 Rendezvous Point (RP): 188 An RP is a router that has been configured to be used as the root 189 of the non-source-specific distribution tree for a multicast 190 group. Join messages from receivers for a group are sent towards 191 the RP, and data from senders is sent to the RP so that receivers 192 can discover who the senders are, and start to receive traffic 193 destined for the group. 195 Designated Router (DR): 196 A shared-media LAN like Ethernet may have multiple PIM-SM routers 197 connected to it. A single one of these routers, the DR, will act 198 on behalf of directly connected hosts with respect to the PIM-SM 199 protocol. A single DR is elected per interface (LAN or otherwise) 200 using a simple election process. 202 MRIB Multicast Routing Information Base. This is the multicast 203 topology table, which is typically derived from the unicast 204 routing table, or routing protocols such as MBGP that carry 205 multicast-specific topology information. In PIM-SM, the MRIB is 206 used to decide where to send Join/Prune messages. A secondary 207 function of the MRIB is to provide routing metrics for destination 208 addresses, these metrics are used when sending and processing 209 Assert messages. 211 RPF Neighbor 212 RPF stands for "Reverse Path Forwarding". The RPF Neighbor of a 213 router with respect to an address is the neighbor that the MRIB 214 indicates should be used to forward packets to that address. In 215 the case of a PIM-SM multicast group, the RPF neighbor is the 216 router that a Join message for that group would be directed to, in 217 the absence of modifying Assert state. 219 TIB Tree Information Base. This is the collection of state at a PIM 220 router that has been created by receiving PIM Join/Prune messages, 221 PIM Assert messages, and IGMP or MLD information from local hosts. 222 It essentially stores the state of all multicast distribution 223 trees at that router. 225 MFIB Multicast Forwarding Information Base. The TIB holds all the 226 state that is necessary to forward multicast packets at a router. 227 However, although this specification defines forwarding in terms 228 of the TIB, to actually forward packets using the TIB is very 229 inefficient. Instead a real router implementation will normally 230 build an efficient MFIB from the TIB state to perform forwarding. 231 How this is done is implementation-specific, and is not discussed 232 in this document. 234 Upstream 235 Towards the root of the tree. The root of tree may either be the 236 source or the RP depending on the context. 238 Downstream 239 Away from the root of the tree. 241 2.2. Pseudocode Notation 243 We use set notation in several places in this specification. 245 A (+) B 246 is the union of two sets A and B. 248 A (-) B 249 is the elements of set A that are not in set B. 251 NULL 252 is the empty set or list. 254 In addition, we use C-like syntax: 256 = denotes assignment of a variable. 258 == denotes a comparison for equality. 260 != denotes a comparison for inequality. 262 Braces { and } are used for grouping. 264 3. PIM-SM Protocol Overview 266 This section provides an overview of PIM-SM behavior. It is intended as 267 an introduction to how PIM-SM works, and is NOT definitive. For the 268 definitive specification, see Section 4. 270 PIM relies on an underlying topology-gathering protocol to populate a 271 routing table with routes. This routing table is called the MRIB or 272 Multicast Routing Information Base. The routes in this table may be 273 taken directly from the unicast routing table, or it may be different 274 and provided by a separate routing protocol such as MBGP [9]. Regardless 275 of how it is created, the primary role of the MRIB in the PIM protocol 276 is to provide the next hop router along a multicast-capable path to each 277 destination subnet. The MRIB is used to determine the next hop neighbor 278 to which any PIM Join/Prune message is sent. Data flows along the 279 reverse path of the Join messages. Thus, in contrast to the unicast RIB 280 which specifies the next hop that a data packet would take to get to 281 some subnet, the MRIB gives reverse-path information, and indicates the 282 path that a multicast data packet would take from its origin subnet to 283 the router that has the MRIB. 285 Like all multicast routing protocols that implement the service model 286 from RFC 1112 [2], PIM-SM must be able to route data packets from 287 sources to receivers without either the sources or receivers knowing a- 288 priori of the existence of the others. This is essentially done in 289 three phases, although as senders and receivers may come and go at any 290 time, all three phases may be occur simultaneously. 292 Phase One: RP Tree 294 In phase one, a multicast receiver expresses its interest in receiving 295 traffic destined for a multicast group. Typically it does this using 296 IGMP [1] or MLD [3], but other mechanisms might also serve this purpose. 297 One of the receiver's local routers is elected as the Designated Router 298 (DR) for that subnet. On receiving the receiver's expression of 299 interest, the DR then sends a PIM Join message towards the RP for that 300 multicast group. This Join message is known as a (*,G) Join because it 301 joins group G for all sources to that group. The (*,G) Join travels 302 hop-by-hop towards the RP for the group, and in each router it passes 303 through, multicast tree state for group G is instantiated. Eventually 304 the (*,G) Join either reaches the RP, or reaches a router that already 305 has (*,G) Join state for that group. When many receivers join the 306 group, their Join messages converge on the RP, and form a distribution 307 tree for group G that is rooted at the RP. This is known as the RP Tree 308 (RPT), and is also known as the shared tree because it is shared by all 309 sources sending to that group. Join messages are resent periodically so 310 long as the receiver remains in the group. When all receivers on a 311 leaf-network leave the group, the DR will send a PIM (*,G) Prune message 312 towards the RP for that multicast group. However if the Prune message is 313 not sent for any reason, the state will eventually time out. 315 A multicast data sender just starts sending data destined for a 316 multicast group. The sender's local router (DR) takes those data 317 packets, unicast-encapsulates them, and sends them directly to the RP. 318 The RP receives these encapsulated data packets, decapsulates them, and 319 forwards them onto the shared tree. The packets then follow the (*,G) 320 multicast tree state in the routers on the RP Tree, being replicated 321 wherever the RP Tree branches, and eventually reaching all the receivers 322 for that multicast group. The process of encapsulating data packets to 323 the RP is called registering, and the encapsulation packets are known as 324 PIM Register packets. 326 At the end of phase one, multicast traffic is flowing encapsulated to 327 the RP, and then natively over the RP tree to the multicast receivers. 329 Phase Two: Register-Stop 331 Register-encapsulation of data packets is inefficient for two reasons: 333 o Encapsulation and decapsulation may be relatively expensive operations 334 for a router to perform, depending on whether or not the router has 335 appropriate hardware for these tasks. 337 o Traveling all the way to the RP, and then back down the shared tree 338 may entail the packets traveling a relatively long distance to reach 339 receivers that are close to the sender. For some applications, this 340 increased latency or bandwidth consumption is undesirable. 342 Although Register-encapsulation may continue indefinitely, for these 343 reasons, the RP will normally choose to switch to native forwarding. To 344 do this, when the RP receives a register-encapsulated data packet from 345 source S on group G, it will normally initiate an (S,G) source-specific 346 Join towards S. This Join message travels hop-by-hop towards S, 347 instantiating (S,G) multicast tree state in the routers along the path. 348 (S,G) multicast tree state is used only to forward packets for group G 349 if those packets come from source S. Eventually the Join message 350 reaches S's subnet or a router that already has (S,G) multicast tree 351 state, and then packets from S start to flow following the (S,G) tree 352 state towards the RP. These data packets may also reach routers with 353 (*,G) state along the path towards the RP - if so, they can short-cut 354 onto the RP tree at this point. 356 While the RP is in the process of joining the source-specific tree for 357 S, the data packets will continue being encapsulated to the RP. When 358 packets from S also start to arrive natively at the the RP, the RP will 359 be receiving two copies of each of these packets. At this point, the RP 360 starts to discard the encapsulated copy of these packets, and it sends a 361 Register-Stop message back to S's DR to prevent the DR unnecessarily 362 encapsulating the packets. 364 At the end of phase 2, traffic will be flowing natively from S along a 365 source-specific tree to the RP, and from there along the shared tree to 366 the receivers. Where the two trees intersect, traffic may transfer from 367 the source-specific tree to the RP tree, and so avoid taking a long 368 detour via the RP. 370 It should be noted that a sender may start sending before or after a 371 receiver joins the group, and thus phase two may happen before the 372 shared tree to the receiver is built. 374 Phase 3: Shortest-Path Tree 376 Although having the RP join back towards the source removes the 377 encapsulation overhead, it does not completely optimize the forwarding 378 paths. For many receivers the route via the RP may involve a 379 significant detour when compared with the shortest path from the source 380 to the receiver. 382 To obtain lower latencies or more efficient bandwidth utilization, a | 383 router on the receiver's LAN, typically the DR, may optionally initiate 384 a transfer from the shared tree to a source-specific shortest-path tree 385 (SPT). To do this, it issues an (S,G) Join towards S. This instantiates 386 state in the routers along the path to S. Eventually this join either 387 reaches S's subnet, or reaches a router that already has (S,G) state. 388 When this happens, data packets from S start to flow following the (S,G) 389 state until they reach the receiver. 391 At this point the receiver (or a router upstream of the receiver) will 392 be receiving two copies of the data - one from the SPT and one from the 393 RPT. When the first traffic starts to arrive from the SPT, the DR or 394 upstream router starts to drop the packets for G from S that arrive via 395 the RP tree. In addition, it sends an (S,G) Prune message towards the 396 RP. This is known as an (S,G,rpt) Prune. The Prune message travels 397 hop-by-hop, instantiating state along the path towards the RP indicating 398 that traffic from S for G should NOT be forwarded in this direction. 399 The prune is propagated until it reaches the RP or a router that still 400 needs the traffic from S for other receivers. 402 By now, the receiver will be receiving traffic from S along the 403 shortest-path tree between the receiver and S. In addition, the RP is 404 receiving the traffic from S, but this traffic is no longer reaching the 405 receiver along the RP tree. As far as the receiver is concerned, this 406 is the final distribution tree. 408 Source-specific Joins 410 IGMPv3 permits a receiver to join a group and specify that it only wants 411 to receive traffic for a group if that traffic comes from a particular 412 source. If a receiver does this, and no other receiver on the LAN 413 requires all the traffic for the group, then the DR may omit performing 414 a (*,G) join to set up the shared tree, and instead issue a source- 415 specific (S,G) join only. 417 The range of multicast addresses from 232.0.0.0 to 232.255.255.255 is 418 currently set aside for source-specific multicast in IPv4. For groups 419 in this range, receivers should only issue source-specific IGMPv3 joins. 420 If a PIM router receives a non-source-specific join for a group in this 421 range, it should ignore it, as described in Section 4.8. 423 Source-specific Prunes 425 IGMPv3 also permits a receiver to join a group and specify that it only 426 wants to receive traffic for a group if that traffic does not come from 427 a specific source or sources. In this case, the DR will perform a (*,G) 428 join as normal, but may combine this with an (S,G,rpt) prune for each of 429 the sources the receiver does not wish to receive. 431 Multi-access Transit LANs 433 The overview so far has concerned itself with point-to-point transit 434 links. However, using multi-access LANs such as Ethernet for transit is 435 not uncommon. This can cause complications for three reasons: 437 o Two or more routers on the LAN may issue (*,G) Joins to different 438 upstream routers on the LAN because they have inconsistent MRIB 439 entries regarding how to reach the RP. Both paths on the RP tree will 440 be set up, causing two copies of all the shared tree traffic to appear 441 on the LAN. 443 o Two or more routers on the LAN may issue (S,G) Joins to different 444 upstream routers on the LAN because they have inconsistent MRIB 445 entries regarding how to reach source S. Both paths on the source- 446 specific tree will be set up, causing two copies of all the traffic 447 from S to appear on the LAN. 449 o A router on the LAN may issue a (*,G) Join to one upstream router on 450 the LAN, and another router on the LAN may issue an (S,G) Join to a 451 different upstream router on the same LAN. Traffic from S may reach 452 the LAN over both the RPT and the SPT. If the receiver behind the 453 downstream (*,G) router doesn't issue an (S,G,rpt) prune, then this 454 condition would persist. 456 All of these problems are caused by there being more than one upstream 457 router with join state for the group or source-group pair. PIM does not 458 prevent such duplicate joins from occurring - instead when duplicate 459 data packets appear on the LAN from different routers, these routers 460 notice this, and then elect a single forwarder. This election is 461 performed using PIM Assert messages, which resolve the problem in favor 462 of the upstream router which has (S,G) state, or if neither or both 463 router has (S,G) state, then in favor of the router with the best metric 464 to the RP for RP trees, or the best metric to the source to source- 465 specific trees. 467 These Assert messages are also received by the downstream routers on the 468 LAN, and these cause subsequent Join messages to be sent to the upstream 469 router that won the Assert. 471 RP Discovery 473 PIM-SM routers need to know the address of the RP for each group for 474 which they have (*,G) state. This address is obtained either 475 automatically (e.g., embedded-RP), through a bootstrap mechanism or 476 through static configuration. 478 One dynamic way to do this is to use the Bootstrap Router (BSR) 479 mechanism [11]. One router in each PIM domain is elected the Bootstrap 480 Router through a simple election process. All the routers in the domain 481 that are configured to be candidates to be RPs periodically unicast 482 their candidacy to the BSR. From the candidates, the BSR picks an RP- 483 set, and periodically announces this set in a Bootstrap message. 484 Bootstrap messages are flooded hop-by-hop throughout the domain until 485 all routers in the domain know the RP-Set. 487 To map a group to an RP, a router hashes the group address into the RP- 488 set using an order-preserving hash function (one that minimizes changes 489 if the RP-Set changes). The resulting RP is the one that it uses as the 490 RP for that group. 492 4. Protocol Specification 494 The specification of PIM-SM is broken into several parts: 496 o Section 4.1 details the protocol state stored. 498 o Section 4.2 specifies the data packet forwarding rules. 500 o Section 4.3. specifies Designated Router (DR) election and the rules 501 for sending and processing Hello messages. 503 o Section 4.4 specifies the PIM Register generation and processing 504 rules. 506 o Section 4.5 specifies the PIM Join/Prune generation and processing 507 rules. 509 o Section 4.6 specifies the PIM Assert generation and processing rules. 511 o Section 4.7 specifies the RP discovery mechanisms. 513 o The subset of PIM required to support Source-Specific Multicast, PIM- 514 SSM, is described in Section 4.8. 516 o PIM packet formats are specified in Section 4.9. 518 o A summary of PIM-SM timers and their default values is given in 519 Section 4.10. 521 o Appendix A in Section 11 specifies the PIM Multicast Border Router 522 behavior. 524 4.1. PIM Protocol State 526 This section specifies all the protocol state that a PIM implementation 527 should maintain in order to function correctly. We term this state the 528 Tree Information Base or TIB, as it holds the state of all the multicast 529 distribution trees at this router. In this specification we define PIM 530 mechanisms in terms of the TIB. However, only a very simple 531 implementation would actually implement packet forwarding operations in 532 terms of this state. Most implementations will use this state to build 533 a multicast forwarding table, which would then be updated when the 534 relevant state in the TIB changes. 536 Although we specify precisely the state to be kept, this does not mean 537 that an implementation of PIM-SM needs to hold the state in this form. 538 This is actually an abstract state definition, which is needed in order 539 to specify the router's behavior. A PIM-SM implementation is free to 540 hold whatever internal state it requires, and will still be conformant 541 with this specification so long as it results in the same externally 542 visible protocol behavior as an abstract router that holds the following 543 state. 545 We divide TIB state into four sections: 547 (*,*,RP) state 548 State that maintains per-RP trees, for all groups served by a given 549 RP. 551 (*,G) state 552 State that maintains the RP tree for G. 554 (S,G) state 555 State that maintains a source-specific tree for source S and group 556 G. 558 (S,G,rpt) state 559 State that maintains source-specific information about source S on 560 the RP tree for G. For example, if a source is being received on 561 the source-specific tree, it will normally have been pruned off the 562 RP tree. This prune state is (S,G,rpt) state. 564 The state that should be kept is described below. Of course, 565 implementations will only maintain state when it is relevant to 566 forwarding operations - for example, the "NoInfo" state might be assumed 567 from the lack of other state information, rather than being held 568 explicitly. 570 4.1.1. General Purpose State 572 A router holds the following non-group-specific state: 574 For each interface: 576 o Override Interval 578 o Propagation Delay 579 o Suppression state: One of {"Enable", "Disable"} 581 Neighbor State: 583 For each neighbor: 585 o Information from neighbor's Hello 587 o Neighbor's GenID. 589 o Neighbor Liveness Timer (NLT) 591 Designated Router (DR) State: 593 o Designated Router's IP Address 595 o DR's DR Priority 597 The Override Interval, the Propagation Delay and the Interface 598 suppression state are described in Section 4.3.3. Designated Router 599 state is described in Section 4.3. 601 4.1.2. (*,*,RP) State 603 For every RP a router keeps the following state: 605 (*,*,RP) state: 606 For each interface: 608 PIM (*,*,RP) Join/Prune State: 610 o State: One of {"NoInfo" (NI), "Join" (J), "Prune- 611 Pending" (PP)} 613 o Prune-Pending Timer (PPT) 615 o Join/Prune Expiry Timer (ET) 617 Not interface specific: 619 Upstream (*,*,RP) Join/Prune State: 621 o State: One of {"NotJoined(*,*,RP)", 622 "Joined(*,*,RP)"} 624 o Upstream Join/Prune Timer (JT) 625 o Last RPF Neighbor towards RP that was used 627 PIM (*,*,RP) Join/Prune state is the result of receiving PIM (*,*,RP) 628 Join/Prune messages on this interface, and is specified in Section 629 4.5.1. 631 The upstream (*,*,RP) Join/Prune State reflects the state of the 632 upstream (*,*,RP) state machine described in Section 4.5.5. 634 The upstream (*,*,RP) Join/Prune Timer is used to send out periodic 635 Join(*,*,RP) messages, and to override Prune(*,*,RP) messages from peers 636 on an upstream LAN interface. 638 The last RPF neighbor towards the RP is stored because if the MRIB 639 changes then the RPF neighbor towards the RP may change. If it does so, 640 then we need to trigger a new Join(*,*,RP) to the new upstream neighbor 641 and a Prune(*,*,RP) to the old upstream neighbor. Similarly, if a 642 router detects through a changed GenID in a Hello message that the 643 upstream neighbor towards the RP has rebooted, then it should re- 644 instantiate state by sending a Join(*,*,RP). These mechanisms are 645 specified in Section 4.5.5. 647 4.1.3. (*,G) State 649 For every group G a router keeps the following state: 651 (*,G) state: 652 For each interface: 654 Local Membership: 655 State: One of {"NoInfo", "Include"} 657 PIM (*,G) Join/Prune State: 659 o State: One of {"NoInfo" (NI), "Join" (J), "Prune- 660 Pending" (PP)} 662 o Prune-Pending Timer (PPT) 664 o Join/Prune Expiry Timer (ET) 666 (*,G) Assert Winner State 668 o State: One of {"NoInfo" (NI), "I lost Assert" (L), 669 "I won Assert" (W)} 671 o Assert Timer (AT) 672 o Assert winner's IP Address (AssertWinner) 674 o Assert winner's Assert Metric (AssertWinnerMetric) 676 Not interface specific: 678 Upstream (*,G) Join/Prune State: 680 o State: One of {"NotJoined(*,G)", "Joined(*,G)"} 682 o Upstream Join/Prune Timer (JT) 684 o Last RP Used 686 o Last RPF Neighbor towards RP that was used 688 Local membership is the result of the local membership mechanism (such 689 as IGMP or MLD) running on that interface. It need not be kept if this 690 router is not the DR on that interface unless this router won a (*,G) 691 assert on this interface for this group, although implementations may 692 optionally keep this state in case they become the DR or assert winner. 693 We recommend storing this information if possible, as it reduces latency 694 converging to stable operating conditions after a failure causing a 695 change of DR. This information is used by the pim_include(*,G) macro 696 described in Section 4.1.6. 698 PIM (*,G) Join/Prune state is the result of receiving PIM (*,G) 699 Join/Prune messages on this interface, and is specified in Section 700 4.5.2. The state is used by the macros that calculate the outgoing 701 interface list in Section 4.1.6, and in the JoinDesired(*,G) macro 702 (defined in Section 4.5.6) that is used in deciding whether a Join(*,G) 703 should be sent upstream. 705 (*,G) Assert Winner state is the result of sending or receiving (*,G) 706 Assert messages on this interface. It is specified in Section 4.6.2. 708 The upstream (*,G) Join/Prune State reflects the state of the upstream 709 (*,G) state machine described in Section 4.5.6. 711 The upstream (*,G) Join/Prune Timer is used to send out periodic 712 Join(*,G) messages, and to override Prune(*,G) messages from peers on an 713 upstream LAN interface. 715 The last RP used must be stored because if the RP-Set changes (Section 716 4.7) then state must be torn down and rebuilt for groups whose RP 717 changes. 719 The last RPF neighbor towards the RP is stored because if the MRIB 720 changes then the RPF neighbor towards the RP may change. If it does so, 721 then we need to trigger a new Join(*,G) to the new upstream neighbor and 722 a Prune(*,G) to the old upstream neighbor. Similarly, if a router 723 detects through a changed GenID in a Hello message that the upstream 724 neighbor towards the RP has rebooted, then it should re-instantiate 725 state by sending a Join(*,G). These mechanisms are specified in Section 726 4.5.6. 728 4.1.4. (S,G) State 730 For every source/group pair (S,G) a router keeps the following state: 732 (S,G) state: 734 For each interface: 736 Local Membership: 737 State: One of {"NoInfo", "Include"} 739 PIM (S,G) Join/Prune State: 741 o State: One of {"NoInfo" (NI), "Join" (J), "Prune- 742 Pending" (PP)} 744 o Prune-Pending Timer (PPT) 746 o Join/Prune Expiry Timer (ET) 748 (S,G) Assert Winner State 750 o State: One of {"NoInfo" (NI), "I lost Assert" (L), 751 "I won Assert" (W)} 753 o Assert Timer (AT) 755 o Assert winner's IP Address (AssertWinner) 757 o Assert winner's Assert Metric (AssertWinnerMetric) 759 Not interface specific: 761 Upstream (S,G) Join/Prune State: 763 o State: One of {"NotJoined(S,G)", "Joined(S,G)"} 765 o Upstream (S,G) Join/Prune Timer (JT) 766 o Last RPF Neighbor towards S that was used 768 o SPTbit (indicates (S,G) state is active) 770 o (S,G) Keepalive Timer (KAT) 772 Additional (S,G) state at the DR: 774 o Register state: One of {"Join" (J), "Prune" (P), 775 "Join-Pending" (JP), "NoInfo" (NI)} 777 o Register-Stop timer 779 Additional (S,G) state at the RP: 781 o PMBR: the first PMBR to send a Register for this 782 source with the Border bit set. 784 Local membership is the result of the local source-specific membership 785 mechanism (such as IGMP version 3) running on that interface and 786 specifying that this particular source should be included. As stored 787 here, this state is the resulting state after any IGMPv3 inconsistencies 788 have been resolved. It need not be kept if this router is not the DR on 789 that interface unless this router won a (S,G) assert on this interface 790 for this group. However, we recommend storing this information if 791 possible, as it reduces latency converging to stable operating 792 conditions after a failure causing a change of DR. This information is 793 used by the pim_include(S,G) macro described in Section 4.1.6. 795 PIM (S,G) Join/Prune state is the result of receiving PIM (S,G) 796 Join/Prune messages on this interface, and is specified in Section 797 4.5.2. The state is used by the macros that calculate the outgoing 798 interface list in Section 4.1.6, and in the JoinDesired(S,G) macro 799 (defined in Section 4.5.7) that is used in deciding whether a Join(S,G) 800 should be sent upstream. 802 (S,G) Assert Winner state is the result of sending or receiving (S,G) 803 Assert messages on this interface. It is specified in Section 4.6.1. 805 The upstream (S,G) Join/Prune State reflects the state of the upstream 806 (S,G) state machine described in Section 4.5.7. 808 The upstream (S,G) Join/Prune Timer is used to send out periodic 809 Join(S,G) messages, and to override Prune(S,G) messages from peers on an 810 upstream LAN interface. 812 The last RPF neighbor towards S is stored because if the MRIB changes 813 then the RPF neighbor towards S may change. If it does so, then we need 814 to trigger a new Join(S,G) to the new upstream neighbor and a Prune(S,G) 815 to the old upstream neighbor. Similarly, if the router detects through 816 a changed GenID in a Hello message that the upstream neighbor towards S 817 has rebooted, then it should re-instantiate state by sending a 818 Join(S,G). These mechanisms are specified in Section 4.5.7. 820 The SPTbit is used to indicate whether forwarding is taking place on the 821 (S,G) Shortest Path Tree (SPT) or on the (*,G) tree. A router can have 822 (S,G) state and still be forwarding on (*,G) state during the interval 823 when the source-specific tree is being constructed. When SPTbit is 824 FALSE, only (*,G) forwarding state is used to forward packets from S to 825 G. When SPTbit is TRUE, both (*,G) and (S,G) forwarding state are used. 827 The (S,G) Keepalive Timer is updated by data being forwarded using this 828 (S,G) forwarding state. It is used to keep (S,G) state alive in the 829 absence of explicit (S,G) Joins. Amongst other things, this is 830 necessary for the so-called "turnaround rules" - when the RP uses (S,G) 831 joins to stop encapsulation, and then (S,G) prunes to prevent traffic 832 from unnecessarily reaching the RP. 834 On a DR, the (S,G) Register State is used to keep track of whether to 835 encapsulate data to the RP on the Register Tunnel; the (S,G) Register- 836 Stop timer tracks how long before encapsulation begins again for a given 837 (S,G). 839 On an RP, the PMBR value must be cleared when the Keepalive Timer 840 expires. 842 4.1.5. (S,G,rpt) State 844 For every source/group pair (S,G) for which a router also has (*,G) 845 state, it also keeps the following state: 847 (S,G,rpt) state: 849 For each interface: 851 Local Membership: 852 State: One of {"NoInfo", "Exclude"} 854 PIM (S,G,rpt) Join/Prune State: 856 o State: One of {"NoInfo", "Pruned", "Prune- 857 Pending"} 859 o Prune-Pending Timer (PPT) 861 o Join/Prune Expiry Timer (ET) 863 Not interface specific: 865 Upstream (S,G,rpt) Join/Prune State: 867 o State: One of {"RPTNotJoined(G)", 868 "NotPruned(S,G,rpt)", "Pruned(S,G,rpt)"} 870 o Override Timer (OT) 872 Local membership is the result of the local source-specific membership 873 mechanism (such as IGMPv3) running on that interface and specifying that 874 although there is (*,G) Include state, this particular source should be 875 excluded. As stored here, this state is the resulting state after any 876 IGMPv3 inconsistencies between LAN members have been resolved. It need 877 not be kept if this router is not the DR on that interface unless this 878 router won a (*,G) assert on this interface for this group. However, we 879 recommend storing this information if possible, as it reduces latency 880 converging to stable operating conditions after a failure causing a 881 change of DR. This information is used by the pim_exclude(S,G) macro 882 described in Section 4.1.6. 884 PIM (S,G,rpt) Join/Prune state is the result of receiving PIM (S,G,rpt) 885 Join/Prune messages on this interface, and is specified in Section 886 4.5.4. The state is used by the macros that calculate the outgoing 887 interface list in Section 4.1.6, and in the rules for adding 888 Prune(S,G,rpt) messages to Join(*,G) messages specified in Section 889 4.5.8. 891 The upstream (S,G,rpt) Join/Prune state is used along with the Override 892 Timer to send the correct override messages in response to Join/Prune 893 messages sent by upstream peers on a LAN. This state and behavior are 894 specified in Section 4.5.9. 896 4.1.6. State Summarization Macros 898 Using this state, we define the following "macro" definitions which we 899 will use in the descriptions of the state machines and pseudocode in the 900 following sections. 902 The most important macros are those that define the outgoing interface 903 list (or "olist") for the relevant state. An olist can be "immediate" 904 if it is built directly from the state of the relevant type. For 905 example, the immediate_olist(S,G) is the olist that would be built if 906 the router only had (S,G) state and no (*,G) or (S,G,rpt) state. In 907 contrast, the "inherited" olist inherits state from other types. For 908 example, the inherited_olist(S,G) is the olist that is relevant for 909 forwarding a packet from S to G using both source-specific and group- 910 specific state. 912 There is no immediate_olist(S,G,rpt) as (S,G,rpt) state is negative 913 state - it removes interfaces in the (*,G) olist from the olist that is 914 actually used to forward traffic. The inherited_olist(S,G,rpt) is 915 therefore the olist that would be used for a packet from S to G 916 forwarding on the RP tree. It is a strict subset of 917 (immediate_olist(*,*,RP) (+) immediate_olist(*,G)). 919 Generally speaking, the inherited olists are used for forwarding, and 920 the immediate_olists are used to make decisions about state maintenance. 922 immediate_olist(*,*,RP) = 923 joins(*,*,RP) 925 immediate_olist(*,G) = 926 joins(*,G) (+) pim_include(*,G) (-) lost_assert(*,G) 928 immediate_olist(S,G) = 929 joins(S,G) (+) pim_include(S,G) (-) lost_assert(S,G) 931 inherited_olist(S,G,rpt) = 932 ( joins(*,*,RP(G)) (+) joins(*,G) (-) prunes(S,G,rpt) ) 933 (+) ( pim_include(*,G) (-) pim_exclude(S,G)) 934 (-) ( lost_assert(*,G) (+) lost_assert(S,G,rpt) ) 936 inherited_olist(S,G) = | 937 inherited_olist(S,G,rpt) (+) | 938 joins(S,G) (+) pim_include(S,G) (-) lost_assert(S,G) 940 The macros pim_include(*,G) and pim_include(S,G) indicate the interfaces 941 to which traffic might be forwarded because of hosts that are local 942 members on that interface. Note that normally only the DR cares about 943 local membership, but when an assert happens, the assert winner takes 944 over responsibility for forwarding traffic to local members that have 945 requested traffic on a group or source/group pair. 947 pim_include(*,G) = 948 { all interfaces I such that: 949 ( ( I_am_DR( I ) AND lost_assert(*,G,I) == FALSE ) 950 OR AssertWinner(*,G,I) == me ) 951 AND local_receiver_include(*,G,I) } 953 pim_include(S,G) = 954 { all interfaces I such that: 955 ( (I_am_DR( I ) AND lost_assert(S,G,I) == FALSE ) 956 OR AssertWinner(S,G,I) == me ) 957 AND local_receiver_include(S,G,I) } 959 pim_exclude(S,G) = 960 { all interfaces I such that: | 961 ( (I_am_DR( I ) AND lost_assert(*,G,I) == FALSE ) | 962 OR AssertWinner(*,G,I) == me ) | 964 AND local_receiver_exclude(S,G,I) } 966 The clause "local_receiver_include(S,G,I)" is true if the IGMP/MLD 967 module or other local membership mechanism has determined that local | 968 members on interface I desire to receive traffic sent specifically by S 969 to G. "local_receiver_include(*,G,I)" is true if the IGMP/MLD module or 970 other local membership mechanism has determined that local members on | 971 interface I desire to receive all traffic sent to G (possibly excluding | 972 traffic from a specific set of sources). "local_receiver_exclude(S,G,I) | 973 is true if "local_receiver_include(*,G,I)" is true but none of the local 974 members desire to receive traffic from S. 976 The set "joins(*,*,RP)" is the set of all interfaces on which the router 977 has received (*,*,RP) Joins: 979 joins(*,*,RP) = 980 { all interfaces I such that 981 DownstreamJPState(*,*,RP,I) is either Join or 982 Prune-Pending } 984 DownstreamJPState(*,*,RP,I) is the state of the finite state machine in 985 Section 4.5.1. 987 The set "joins(*,G)" is the set of all interfaces on which the router 988 has received (*,G) Joins: 990 joins(*,G) = 991 { all interfaces I such that 992 DownstreamJPState(*,G,I) is either Join or Prune-Pending } 994 DownstreamJPState(*,G,I) is the state of the finite state machine in 995 Section 4.5.2. 997 The set "joins(S,G)" is the set of all interfaces on which the router 998 has received (S,G) Joins: 1000 joins(S,G) = 1001 { all interfaces I such that 1002 DownstreamJPState(S,G,I) is either Join or Prune-Pending } 1004 DownstreamJPState(S,G,I) is the state of the finite state machine in 1005 Section 4.5.3. 1007 The set "prunes(S,G,rpt)" is the set of all interfaces on which the 1008 router has received (*,G) joins and (S,G,rpt) prunes. 1010 prunes(S,G,rpt) = 1011 { all interfaces I such that 1012 DownstreamJPState(S,G,rpt,I) is Prune or PruneTmp } 1014 DownstreamJPState(S,G,rpt,I) is the state of the finite state machine in 1015 Section 4.5.4. 1017 The set "lost_assert(*,G)" is the set of all interfaces on which the 1018 router has received (*,G) joins but has lost a (*,G) assert. The macro 1019 lost_assert(*,G,I) is defined in Section 4.6.5. 1021 lost_assert(*,G) = 1022 { all interfaces I such that 1023 lost_assert(*,G,I) == TRUE } 1025 The set "lost_assert(S,G,rpt)" is the set of all interfaces on which the 1026 router has received (*,G) joins but has lost an (S,G) assert. The macro 1027 lost_assert(S,G,rpt,I) is defined in Section 4.6.5. 1029 lost_assert(S,G,rpt) = 1030 { all interfaces I such that 1031 lost_assert(S,G,rpt,I) == TRUE } 1033 The set "lost_assert(S,G)" is the set of all interfaces on which the 1034 router has received (S,G) joins but has lost an (S,G) assert. The macro 1035 lost_assert(S,G,I) is defined in Section 4.6.5. 1037 lost_assert(S,G) = 1038 { all interfaces I such that 1039 lost_assert(S,G,I) == TRUE } 1041 The following pseudocode macro definitions are also used in many places 1042 in the specification. Basically RPF' is the RPF neighbor towards an RP 1043 or source unless a PIM-Assert has overridden the normal choice of 1044 neighbor. 1046 neighbor RPF'(*,G) { 1047 if ( I_Am_Assert_Loser(*, G, RPF_interface(RP(G))) ) { 1048 return AssertWinner(*, G, RPF_interface(RP(G)) ) 1049 } else { 1050 return NBR( RPF_interface(RP(G)), MRIB.next_hop( RP(G) ) ) 1051 } 1052 } 1054 neighbor RPF'(S,G,rpt) { 1055 if( I_Am_Assert_Loser(S, G, RPF_interface(RP(G)) ) ) { 1056 return AssertWinner(S, G, RPF_interface(RP(G)) ) 1057 } else { 1058 return RPF'(*,G) 1059 } 1060 } 1062 neighbor RPF'(S,G) { 1063 if ( I_Am_Assert_Loser(S, G, RPF_interface(S) )) { 1064 return AssertWinner(S, G, RPF_interface(S) ) 1065 } else { 1066 return NBR( RPF_interface(S), MRIB.next_hop( S ) ) 1067 } 1068 } 1070 RPF'(*,G) and RPF'(S,G) indicate the neighbor from which data packets 1071 should be coming and to which joins should be sent on the RP tree and 1072 SPT respectively. 1074 RPF'(S,G,rpt) is basically RPF'(*,G) modified by the result of an 1075 Assert(S,G) on RPF_interface(RP(G)). In such a case, packets from S 1076 will be originating from a different router than RPF'(*,G). If we only 1077 have active (*,G) Join state, we need to accept packets from 1078 RPF'(S,G,rpt), and add a Prune(S,G,rpt) to the periodic Join(*,G) 1079 messages that we send to RPF'(*,G) (See Section 4.5.8). 1081 The function MRIB.next_hop( S ) returns an address of the next-hop PIM 1082 neighbor toward the host S, as indicated by the current MRIB. If S is 1083 directly adjacent, then MRIB.next_hop( S ) returns NULL. At the RP for 1084 G, MRIB.next_hop( RP(G)) returns NULL. 1086 The function NBR( I, A ) uses information gathered through PIM Hello 1087 messages to map the IP address A of a directly connected PIM neighbor 1088 router on interface I to the primary IP address of the same router 1089 (Section 4.3.4). The primary IP address of a neighbor is the address 1090 that it uses as the source of its PIM Hello messages. Note that a 1091 neighbor's IP address may be non-unique within the PIM neighbor database 1092 due to scope issues. The address must however be unique amongst the 1093 addresses of all the PIM neighbors on a specific interface. 1095 I_Am_Assert_Loser(S, G, I) is true if the Assert state machine (in 1096 Section 4.6.1) for (S,G) on Interface I is in "I am Assert Loser" state. 1098 I_Am_Assert_Loser(*, G, I) is true if the Assert state machine (in 1099 Section 4.6.2) for (*,G) on Interface I is in "I am Assert Loser" state. 1101 4.2. Data Packet Forwarding Rules 1103 The PIM-SM packet forwarding rules are defined below in pseudocode. 1105 iif is the incoming interface of the packet. 1106 S is the source address of the packet. 1107 G is the destination address of the packet (group address). 1108 RP is the address of the Rendezvous Point for this group. 1109 RPF_interface(S) is the interface the MRIB indicates would be used 1110 to route packets to S. 1111 RPF_interface(RP) is the interface the MRIB indicates would be used 1112 to route packets to RP, except at the RP when it is the 1113 decapsulation interface (the "virtual" interface on which register 1114 packets are received). 1116 First, we restart (or start) the Keepalive Timer if the source is on a 1117 directly connected subnet. 1119 Second, we check to see if the SPTbit should be set because we've now 1120 switched from the RP tree to the SPT. 1122 Next we check to see whether the packet should be accepted based on TIB 1123 state and the interface that the packet arrived on. 1125 If the packet should be forwarded using (S,G) state, we then build an 1126 outgoing interface list for the packet. If this list is not empty, then 1127 we restart the (S,G) state Keepalive Timer. 1129 If the packet should be forwarded using (*,*,RP) or (*,G) state, then we 1130 just build an outgoing interface list for the packet. We also check if 1131 we should initiate a switch to start receiving this source on a shortest 1132 path tree. 1134 Finally we remove the incoming interface from the outgoing interface 1135 list we've created, and if the resulting outgoing interface list is not 1136 empty, we forward the packet out of those interfaces. 1138 On receipt of data from S to G on interface iif: 1139 if( DirectlyConnected(S) == TRUE AND iif == RPF_interface(S) ) { 1140 set KeepaliveTimer(S,G) to Keepalive_Period 1141 # Note: a register state transition or UpstreamJPState(S,G) 1142 # transition may happen as a result of restarting 1143 # KeepaliveTimer, and must be dealt with here. 1144 } 1146 if( iif == RPF_interface(S) AND UpstreamJPState(S,G) == Joined AND | 1147 inherited_olist(S,G) != NULL ) { | 1148 set KeepaliveTimer(S,G) to Keepalive_Period | 1149 } | 1151 Update_SPTbit(S,G,iif) 1152 oiflist = NULL 1154 if( iif == RPF_interface(S) AND SPTbit(S,G) == TRUE ) { | 1155 oiflist = inherited_olist(S,G) 1156 } else if( iif == RPF_interface(RP(G)) AND SPTbit(S,G) == FALSE) { 1157 oiflist = inherited_olist(S,G,rpt) 1158 CheckSwitchToSpt(S,G) 1159 } else { 1160 # Note: RPF check failed 1161 # A transition in an Assert FSM, may cause an Assert(S,G) | 1162 # or Assert(*,G) message to be sent out interface iif. | 1163 # See section 4.6 for details. | 1164 if ( SPTbit(S,G) == TRUE AND iif is in inherited_olist(S,G) ) { 1165 send Assert(S,G) on iif 1166 } else if ( SPTbit(S,G) == FALSE AND 1167 iif is in inherited_olist(S,G,rpt) { 1168 send Assert(*,G) on iif 1169 } 1170 } 1172 oiflist = oiflist (-) iif 1173 forward packet on all interfaces in oiflist 1175 This pseudocode employs several "macro" definitions: 1177 DirectlyConnected(S) is TRUE if the source S is on any subnet that is 1178 directly connected to this router (or for packets originating on this 1179 router). 1181 inherited_olist(S,G) and inherited_olist(S,G,rpt) are defined in Section 1182 4.1. 1184 Basically inherited_olist(S,G) is the outgoing interface list for 1185 packets forwarded on (S,G) state taking into account (*,*,RP) state, 1186 (*,G) state, asserts, etc. 1188 inherited_olist(S,G,rpt) is the outgoing interface for packets forwarded 1189 on (*,*,RP) or (*,G) state taking into account (S,G,rpt) prune state, 1190 and asserts, etc. 1192 Update_SPTbit(S,G,iif) is defined in Section 4.2.2. 1194 CheckSwitchToSpt(S,G) is defined in Section 4.2.1. 1196 UpstreamJPState(S,G) is the state of the finite state machine in Section 1197 4.5.7. 1199 Keepalive_Period is defined in Section 4.10. 1201 Data triggered PIM-Assert messages sent from the above forwarding code 1202 should be rate-limited in a implementation-dependent manner. 1204 4.2.1. Last-hop Switchover to the SPT 1206 In Sparse-Mode PIM, last-hop routers join the shared tree towards the 1207 RP. Once traffic from sources to joined groups arrives at a last-hop 1208 router it has the option of switching to receive the traffic on a 1209 shortest path tree (SPT). 1211 The decision for a router to switch to the SPT is controlled as follows: 1213 void 1214 CheckSwitchToSpt(S,G) { 1215 if ( ( pim_include(*,G) (-) pim_exclude(S,G) 1216 (+) pim_include(S,G) != NULL ) 1217 AND SwitchToSptDesired(S,G) ) { 1218 # Note: Restarting the KAT will result in the SPT switch 1219 restart KeepaliveTimer(S,G); 1220 } 1221 } 1223 SwitchToSptDesired(S,G) is a policy function that is implementation 1224 defined. An "infinite threshold" policy can be implemented making 1225 SwitchToSptDesired(S,G) return false all the time. A "switch on first 1226 packet" policy can be implemented by making SwitchToSptDesired(S,G) 1227 return true once a single packet has been received for the source and 1228 group. 1230 4.2.2. Setting and Clearing the (S,G) SPTbit 1232 The (S,G) SPTbit is used to distinguish whether to forward on 1233 (*,*,RP)/(*,G) or on (S,G) state. When switching from the RP tree to 1234 the source tree, there is a transition period when data is arriving due 1235 to upstream (*,*,RP)/(*,G) state while upstream (S,G) state is being 1236 established during which time a router should continue to forward only 1237 on (*,*,RP)/(*,G) state. This prevents temporary black-holes that would 1238 be caused by sending a Prune(S,G,rpt) before the upstream (S,G) state 1239 has finished being established. 1241 Thus, when a packet arrives, the (S,G) SPTbit is updated as follows: 1243 void 1244 Update_SPTbit(S,G,iif) { 1245 if ( iif == RPF_interface(S) 1246 AND JoinDesired(S,G) == TRUE 1247 AND ( DirectlyConnected(S) == TRUE 1248 OR RPF_interface(S) != RPF_interface(RP(G)) 1249 OR inherited_olist(S,G,rpt) == NULL 1250 OR ( ( RPF'(S,G) == RPF'(*,G) ) AND 1251 ( RPF'(S,G) != NULL ) ) 1252 OR ( I_Am_Assert_Loser(S,G,iif) ) { 1253 Set SPTbit(S,G) to TRUE 1254 } 1255 } 1257 Additionally a router can set SPTbit(S,G) to TRUE in other cases, such 1258 as when it receives an Assert(S,G) on RPF_interface(S) (see Section 1259 4.6.1). 1261 JoinDesired(S,G) is defined in Section 4.5.7, and indicates whether we 1262 have the appropriate (S,G) Join state to wish to send a Join(S,G) 1263 upstream. 1265 Basically Update_SPTbit will set the SPTbit if we have the appropriate 1266 (S,G) join state and the packet arrived on the correct upstream 1267 interface for S, and one or more of the following conditions applies: 1269 1. The source is directly connected, in which case the switch to the 1270 SPT is a no-op. 1272 2. The RPF interface to S is different from the RPF interface to the 1273 RP. The packet arrived on RPF_interface(S), and so the SPT must 1274 have been completed. 1276 3. No-one wants the packet on the RP tree. 1278 4. RPF'(S,G) == RPF'(*,G). In this case the router will never be able 1279 to tell if the SPT has been completed, so it should just switch 1280 immediately. 1282 In the case where the RPF interface is the same for the RP and for S, 1283 but RPF'(S,G) and RPF'(*,G) differ, then we wait for an Assert(S,G) 1284 which indicates that the upstream router with (S,G) state believes the 1285 SPT has been completed. However item (3) above is needed because there 1286 may not be any (*,G) state to trigger an Assert(S,G) to happen. 1288 The SPTbit is cleared in the (S,G) upstream state machine (see Section 1289 4.5.7) when JoinDesired(S,G) becomes FALSE. 1291 4.3. Designated Routers (DR) and Hello Messages 1293 A shared-media LAN like Ethernet may have multiple PIM-SM routers 1294 connected to it. A single one of these routers, the DR, will act on 1295 behalf of directly connected hosts with respect to the PIM-SM protocol. 1296 Because the distinction between LANs and point-to-point interfaces can 1297 sometimes be blurred, and because routers may also have multicast host 1298 functionality, the PIM-SM specification makes no distinction between the 1299 two. Thus DR election will happen on all interfaces, LAN or otherwise. 1301 DR election is performed using Hello messages. Hello messages are also 1302 the way that option negotiation takes place in PIM, so that additional 1303 functionality can be enabled, or parameters tuned. 1305 4.3.1. Sending Hello Messages 1307 PIM Hello messages are sent periodically on each PIM-enabled interface. 1308 They allow a router to learn about the neighboring PIM routers on each 1309 interface. Hello messages are also the mechanism used to elect a 1310 Designated Router (DR), and to negotiate additional capabilities. A 1311 router must record the Hello information received from each PIM 1312 neighbor. 1314 Hello messages MUST be sent on all active interfaces, including physical 1315 point-to-point links, and are multicast to the `ALL-PIM-ROUTERS' group 1316 address (`224.0.0.13' for IPv4 and `ff02::d' for IPv6). 1318 We note that some implementations do not send Hello messages 1319 on point-to-point interfaces. This is non-compliant behavior. 1320 A compliant PIM router MUST send Hello messages, even on 1321 point-to-point interfaces. 1323 A per interface Hello Timer (HT(I)) is used to trigger sending Hello 1324 messages on each active interface. When PIM is enabled on an interface 1325 or a router first starts, the Hello Timer of that interface is set to a 1326 random value between 0 and Triggered_Hello_Delay. This prevents 1327 synchronization of Hello messages if multiple routers are powered on 1328 simultaneously. After the initial randomized interval, Hello messages 1329 must be sent every Hello_Period seconds. The Hello Timer should not be 1330 reset except when it expires. 1332 Note that neighbors will not accept Join/Prune or Assert messages from a 1333 router unless they have first heard a Hello message from that router. 1334 Thus if a router needs to send a Join/Prune or Assert message on an 1335 interface on which it has not yet sent a Hello message with the 1336 currently configured IP address, then it MUST immediately send the 1337 relevant Hello message without waiting for the Hello Timer to expire, 1338 followed by the Join/Prune or Assert message. 1340 The DR_Priority Option allows a network administrator to give preference 1341 to a particular router in the DR election process by giving it a 1342 numerically larger DR Priority. The DR_Priority Option SHOULD be 1343 included in every Hello message, even if no DR Priority is explicitly 1344 configured on that interface. This is necessary because priority-based 1345 DR election is only enabled when all neighbors on an interface advertise 1346 that they are capable of using the DR_Priority Option. The default 1347 priority is 1. 1349 The Generation_Identifier (GenID) Option SHOULD be included in all Hello 1350 messages. The GenID option contains a randomly generated 32-bit value 1351 that is regenerated each time PIM forwarding is started or restarted on 1352 the interface, including when the router itself restarts. When a Hello 1353 message with a new GenID is received from a neighbor, any old Hello 1354 information about that neighbor SHOULD be discarded and superseded by 1355 the information from the new Hello message. This may cause a new DR to 1356 be chosen on that interface. 1358 The LAN Prune Delay Option SHOULD be included in all Hello messages sent 1359 on multi-access LANs. This option advertises a router's capability to 1360 use values other than the default for the Propagation_Delay and 1361 Override_Interval which affect the setting of the Prune-Pending, 1362 Upstream Join and Override Timers (defined in Section 4.10). 1364 The Interface_Address_List Option advertises all the secondary addresses 1365 associated with the source interface of the router originating the 1366 message. The option MUST be included in all Hello messages if there are 1367 secondary addresses associated with the source interface and MAY be 1368 omitted if no secondary addresses exist. 1370 To allow new or rebooting routers to learn of PIM neighbors quickly, 1371 when a Hello message is received from a new neighbor, or a Hello message 1372 with a new GenID is received from an existing neighbor, a new Hello 1373 message should be sent on this interface after a randomized delay 1374 between 0 and Triggered_Hello_Delay. This triggered message need not 1375 change the timing of the scheduled periodic message. If a router needs 1376 to send a Join/Prune to the new neighbor or send an Assert message in 1377 response to an Assert message from the new neighbor before this 1378 randomized delay has expired, then it MUST immediately send the relevant 1379 Hello message without waiting for the Hello Timer to expire, followed by 1380 the Join/Prune or Assert message. If it does not do this, then the new 1381 neighbor will discard the Join/Prune or Assert message. 1383 Before an interface goes down or changes primary IP address, a Hello 1384 message with a zero HoldTime should be sent immediately (with the old IP 1385 address if the IP address changed). This will cause PIM neighbors to 1386 remove this neighbor (or its old IP address) immediately. After an 1387 interface has changed its IP address, it MUST send a Hello message with 1388 its new IP address. If an interface changes one of its secondary IP 1389 addresses, a Hello message with an updated Address_List option and a 1390 non-zero HoldTime should be sent immediately. This will cause PIM 1391 neighbors to update this neighbor's list of secondary addresses 1392 immediately. 1394 4.3.2. DR Election 1396 When a PIM Hello message is received on interface I the following 1397 information about the sending neighbor is recorded: 1399 neighbor.interface 1400 The interface on which the Hello message arrived. 1402 neighbor.primary_ip_address 1403 The IP address that the PIM neighbor used as the source 1404 address of the Hello message. 1406 neighbor.genid 1407 The Generation ID of the PIM neighbor. 1409 neighbor.dr_priority 1410 The DR Priority field of the PIM neighbor if it is present in 1411 the Hello message. 1413 neighbor.dr_priority_present 1414 A flag indicating if the DR Priority field was present in the 1415 Hello message. 1417 neighbor.timeout 1418 A timer value to time out the neighbor state when it becomes 1419 stale. 1420 The Neighbor Liveness Timer (NLT(N,I)) is reset to 1421 Hello_Holdtime (from the Hello Holdtime option) whenever a 1422 Hello message is received containing a Holdtime option, or to 1423 Default_Hello_Holdtime if the Hello message does not contain 1424 the Holdtime option. 1426 Neighbor state is deleted when the neighbor timeout expires. 1428 The function for computing the DR on interface I is: 1430 host 1431 DR(I) { 1432 dr = me 1433 for each neighbor on interface I { 1434 if ( dr_is_better( neighbor, dr, I ) == TRUE ) { 1435 dr = neighbor 1436 } 1437 } 1438 return dr 1439 } 1441 The function used for comparing DR "metrics" on interface I is: 1443 bool 1444 dr_is_better(a,b,I) { 1445 if( there is a neighbor n on I for which n.dr_priority_present 1446 is false ) { 1447 return a.primary_ip_address > b.primary_ip_address 1448 } else { 1449 return ( a.dr_priority > b.dr_priority ) OR 1450 ( a.dr_priority == b.dr_priority AND 1451 a.primary_ip_address > b.primary_ip_address ) 1452 } 1453 } 1455 The trivial function I_am_DR(I) is defined to aid readability: 1457 bool 1458 I_am_DR(I) { 1459 return DR(I) == me 1460 } 1462 The DR Priority is a 32-bit unsigned number and the numerically larger 1463 priority is always preferred. A router's idea of the current DR on an 1464 interface can change when a PIM Hello message is received, when a 1465 neighbor times out, or when a router's own DR Priority changes. If the 1466 router becomes the DR or ceases to be the DR, this will normally cause 1467 the DR Register state machine to change state. Subsequent actions are 1468 determined by that state machine. 1470 We note that some PIM implementations do not send Hello 1471 messages on point-to-point interfaces, and so cannot perform 1472 DR election on such interfaces. This in non-compliant 1473 behavior. DR election MUST be performed on ALL active PIM-SM 1474 interfaces. 1476 4.3.3. Reducing Prune Propagation Delay on LANs 1478 In addition to the information recorded for the DR Election, the 1479 following per neighbor information is obtained from the LAN Prune Delay 1480 Hello option: 1482 neighbor.lan_prune_delay_present 1483 A flag indicating if the LAN Prune Delay option was present in 1484 the Hello message. 1486 neighbor.tracking_support 1487 A flag storing the value of the T bit in the LAN Prune Delay 1488 option if it is present in the Hello message. This indicates 1489 the neighbor's capability to disable Join message suppression. 1491 neighbor.propagation_delay 1492 The Propagation Delay field of the LAN Prune Delay option (if 1493 present) in the Hello message. 1495 neighbor.override_interval 1496 The Override_Interval field of the LAN Prune Delay option (if 1497 present) in the Hello message. 1499 The additional state described above is deleted along with the DR 1500 neighbor state when the neighbor timeout expires. 1502 Just like the DR_Priority option, the information provided in the LAN 1503 Prune Delay option is not used unless all neighbors on a link advertise 1504 the option. The function below computes this state: 1506 bool 1507 lan_delay_enabled(I) { 1508 for each neighbor on interface I { 1509 if ( neighbor.lan_prune_delay_present == false ) { 1510 return false 1511 } 1512 } 1513 return true 1514 } 1516 The Propagation Delay inserted by a router in the LAN Prune Delay option | 1517 expresses the expected message propagation delay on the link and should 1518 be configurable by the system administrator. It is used by upstream 1519 routers to figure out how long they should wait for a Join override 1520 message before pruning an interface. 1522 PIM implementors should enforce a lower bound on the permitted values 1523 for this delay to allow for scheduling and processing delays within 1524 their router. Such delays may cause received messages to be processed 1525 later as well as triggered messages to be sent later than intended. 1526 Setting this Propagation Delay to too low a value may result in 1527 temporary forwarding outages because a downstream router will not be 1528 able to override a neighbor's Prune message before the upstream neighbor 1529 stops forwarding. 1531 When all routers on a link are in a position to negotiate a different 1532 than default Propagation Delay, the largest value from those advertised 1533 by each neighbor is chosen. The function for computing the 1534 Effective_Propagation_Delay of interface I is: 1536 time_interval 1537 Effective_Propagation_Delay(I) { 1538 if ( lan_delay_enabled(I) == false ) { 1539 return Propagation_delay_default 1540 } 1541 delay = Propagation_Delay(I) 1542 for each neighbor on interface I { 1543 if ( neighbor.propagation_delay > delay ) { 1544 delay = neighbor.propagation_delay 1545 } 1546 } 1547 return delay 1548 } 1550 To avoid synchronization of override messages when multiple downstream 1551 routers share a multi-access link, sending of such messages is delayed 1552 by a small random amount of time. The period of randomization should 1553 represent the size of the PIM router population on the link. Each 1554 router expresses its view of the amount of randomization necessary in 1555 the Override Interval field of the LAN Prune Delay option. 1557 When all routers on a link are in a position to negotiate a different 1558 than default Override Interval, the largest value from those advertised 1559 by each neighbor is chosen. The function for computing the Effective 1560 Override Interval of interface I is: 1562 time_interval 1563 Effective_Override_Interval(I) { 1564 if ( lan_delay_enabled(I) == false ) { 1565 return t_override_default 1566 } 1567 delay = Override_Interval(I) 1568 for each neighbor on interface I { 1569 if ( neighbor.override_interval > delay ) { 1570 delay = neighbor.override_interval 1571 } 1572 } 1573 return delay 1574 } 1576 Although the mechanisms are not specified in this document, it is 1577 possible for upstream routers to explicitly track the join membership of 1578 individual downstream routers if Join suppression is disabled. A router 1579 can advertise its willingness to disable Join suppression by using the T 1580 bit in the LAN Prune Delay Hello option. Unless all PIM routers on a 1581 link negotiate this capability, explicit tracking and the disabling of 1582 the Join suppression mechanism are not possible. The function for 1583 computing the state of Suppression on interface I is: 1585 bool 1586 Suppression_Enabled(I) { 1587 if ( lan_delay_enabled(I) == false ) { 1588 return true 1589 } 1590 for each neighbor on interface I { 1591 if ( neighbor.tracking_support == false ) { 1592 return true 1593 } 1594 } 1595 return false 1596 } 1598 Note that the setting of Suppression_Enabled(I) affects the value of 1599 t_suppressed (see Section 4.10). 1601 4.3.4. Maintaining Secondary Address Lists 1603 Communication of a router's interface secondary addresses to its PIM 1604 neighbors is necessary to provide the neighbors with a mechanism for 1605 mapping next_hop information obtained through their MRIB to a primary 1606 address that can be used as a destination for Join/Prune messages. The 1607 mapping is performed through the NBR macro. The primary address of a 1608 PIM neighbor is obtained from the source IP address used in its PIM 1609 Hello messages. Secondary addresses are carried within the Hello message 1610 in an Address List Hello option. The primary address of the source 1611 interface of the router MUST NOT be listed within the Address List Hello 1612 option. 1614 In addition to the information recorded for the DR Election, the 1615 following per neighbor information is obtained from the Address List 1616 Hello option: 1618 neighbor.secondary_address_list 1619 The list of secondary addresses used by the PIM neighbor on 1620 the interface through which the Hello message was transmitted. 1622 When processing a received PIM Hello message containing an Address List 1623 Hello option, the list of secondary addresses in the message completely 1624 replaces any previously associated secondary addresses for that 1625 neighbor. If a received PIM Hello message does not contain an Address 1626 List Hello option then all secondary addresses associated with the 1627 neighbor must be deleted. If a received PIM Hello message contains an 1628 Address List Hello option that includes the primary address of the 1629 sending router in the list of secondary addresses (although this is not 1630 expected) then the addresses listed in the message excluding the primary 1631 address are used to update the associated secondary addresses for that 1632 neighbor. 1634 All the advertised secondary addresses in received Hello messages must 1635 be checked against those previously advertised by all other PIM 1636 neighbors on that interface. If there is a conflict and the same 1637 secondary address was previously advertised by another neighbor then 1638 only the most recently received mapping MUST be maintained and an error 1639 message SHOULD be logged to the administrator in a rate limited manner. 1641 Within one Address List Hello option, all the addresses MUST be of the 1642 same address family. It is not permitted to mix IPv4 and IPv6 addresses 1643 within the same message. In addition, the address family of the fields 1644 in the message SHOULD be the same as the IP source and destination 1645 addresses of the packet header. 1647 4.4. PIM Register Messages 1649 Overview 1651 The Designated Router (DR) on a LAN or point-to-point link encapsulates 1652 multicast packets from local sources to the RP for the relevant group 1653 unless it recently received a Register-Stop message for that (S,G) or 1654 (*,G) from the RP. When the DR receives a Register-Stop message from 1655 the RP, it starts a Register-Stop Timer to maintain this state. Just 1656 before the Register-Stop Timer expires, the DR sends a Null-Register 1657 Message to the RP to allow the RP to refresh the Register-Stop 1658 information at the DR. If the Register-Stop Timer actually expires, the 1659 DR will resume encapsulating packets from the source to the RP. 1661 4.4.1. Sending Register Messages from the DR 1663 Every PIM-SM router has the capability to be a DR. The state machine 1664 below is used to implement Register functionality. For the purposes of 1665 specification, we represent the mechanism to encapsulate packets to the 1666 RP as a Register-Tunnel interface, which is added to or removed from the 1667 (S,G) olist. The tunnel interface then takes part in the normal packet 1668 forwarding rules as specified in Section 4.2. 1670 If register state is maintained, it is maintained only for directly 1671 connected sources, and is per-(S,G). There are four states in the DR's 1672 per-(S,G) Register state machine: 1674 Join (J) 1675 The register tunnel is "joined" (the join is actually implicit, but 1676 the DR acts as if the RP has joined the DR on the tunnel 1677 interface). 1679 Prune (P) 1680 The register tunnel is "pruned" (this occurs when a Register-Stop 1681 is received). 1683 Join-Pending (JP) 1684 The register tunnel is pruned but the DR is contemplating adding it 1685 back. 1687 NoInfo (NI) 1688 No information. This is the initial state, and the state when the 1689 router is not the DR. 1691 In addition, a Register-Stop Timer (RST) is kept if the state machine is 1692 not in the NoInfo state. 1694 Figure 1: Per-(S,G) register state machine at a DR in tabular form 1696 +-----------++---------------------------------------------------------------+ 1697 | || Event | 1698 | ++-----------+------------+------------+------------+------------+ 1699 |Prev State ||Register- | Could | Could | Register- | RP changed | 1700 | ||Stop Timer | Register | Register | Stop | | 1701 | ||expires | ->True | ->False | received | | 1702 +-----------++-----------+------------+------------+------------+------------+ 1703 |NoInfo ||- | -> J state | - | - | - | 1704 |(NI) || | add reg | | | | 1705 | || | tunnel | | | | 1706 +-----------++-----------+------------+------------+------------+------------+ 1707 | ||- | - | -> NI | -> P state | -> J state | 1708 | || | | state | | | 1709 | || | | remove reg | remove reg | update reg | 1710 |Join (J) || | | tunnel | tunnel; | tunnel | 1711 | || | | | set | | 1712 | || | | | Register- | | 1713 | || | | | Stop | | 1714 | || | | | Timer(*) | | 1715 +-----------++-----------+------------+------------+------------+------------+ 1716 | ||-> J state | - | -> NI | -> P state | -> J state | 1717 | || | | state | | | 1718 |Join- ||add reg | | | set | add reg | 1719 |Pending ||tunnel | | | Register- | tunnel; | 1720 |(JP) || | | | Stop | cancel | 1721 | || | | | Timer(*) | Register- | 1722 | || | | | | Stop Timer | 1723 Tim+-----------++-----------+------------+------------+------------+------------+ 1724 | ||-> JP | - | -> NI | - | -> J state | 1725 | ||state | | state | | | 1726 | ||set | | | | add reg | 1727 |Prune (P) ||Register- | | | | tunnel; | 1728 | ||Stop | | | | cancel | 1729 | ||Timer(**); | | | | Register- | 1730 | ||send Null- | | | | Stop Timer | 1731 | ||Register | | | | | 1732 +-----------++-----------+------------+------------+------------+------------+ 1734 Notes: 1736 (*) The Register-Stop Timer is set to a random value chosen uniformly 1737 from the interval ( 0.5 * Register_Suppression_Time, 1.5 * 1738 Register_Suppression_Time) minus Register_Probe_Time; 1740 Subtracting off Register_Probe_Time is a bit unnecessary because it 1741 is really small compared to Register_Suppression_Time, but was in 1742 the old spec and is kept for compatibility. 1744 (**) The Register-Stop Timer is set to Register_Probe_Time. 1746 The following actions are defined: 1748 Add Register Tunnel 1750 A Register-Tunnel virtual interface, VI, is created (if it doesn't 1751 already exist) with its encapsulation target being RP(G). 1752 DownstreamJPState(S,G,VI) is set to Join state, causing the tunnel 1753 interface to be added to immediate_olist(S,G). 1755 Remove Register Tunnel 1757 VI is the Register-Tunnel virtual interface with encapsulation target of 1758 RP(G). DownstreamJPState(S,G,VI) is set to NoInfo state, causing the 1759 tunnel interface to be removed from immediate_olist(S,G). If 1760 DownstreamJPState(S,G,VI) is NoInfo for all (S,G), then VI can be 1761 deleted. 1763 Update Register Tunnel 1765 This action occurs when RP(G) changes. 1767 VI_old is the Register-Tunnel virtual interface with encapsulation 1768 target old_RP(G). A Register-Tunnel virtual interface, VI_new, is 1769 created (if it doesn't already exist) with its encapsulation target 1770 being new_RP(G). DownstreamJPState(S,G,VI_old) is set to NoInfo state 1771 and DownstreamJPState(S,G,VI_new) is set to Join state. If 1772 DownstreamJPState(S,G,VI_old) is NoInfo for all (S,G), then VI_old can 1773 be deleted. 1775 Note that we can not simply change the encapsulation target of VI_old 1776 because not all groups using that encapsulation tunnel will have moved 1777 to the same new RP. 1779 CouldRegister(S,G) 1781 The macro "CouldRegister" in the state machine is defined as: 1783 bool CouldRegister(S,G) { 1784 return ( I_am_DR( RPF_interface(S) ) AND 1785 KeepaliveTimer(S,G) is running AND 1786 DirectlyConnected(S) == TRUE ) 1787 } 1789 Note that on reception of a packet at the DR from a directly connected 1790 source, KeepaliveTimer(S,G) needs to be set by the packet forwarding 1791 rules before computing CouldRegister(S,G) in the register state machine, 1792 or the first packet from a source won't be registered. 1794 Encapsulating data packets in the Register Tunnel 1796 Conceptually, the Register Tunnel is an interface with a smaller MTU 1797 than the underlying IP interface towards the RP. IP fragmentation on 1798 packets forwarded on the Register Tunnel is performed based upon this 1799 smaller MTU. The encapsulating DR may perform Path MTU Discovery to the 1800 RP to determine the effective MTU of the tunnel. Fragmentation for the 1801 smaller MTU should take both the outer IP header and the PIM register 1802 header overhead into account. If a multicast packet is fragmented on 1803 the way into the Register Tunnel, each fragment is encapsulated 1804 individually so it contains IP, PIM, and inner IP headers. 1806 In IPv6, the DR MUST perform Path MTU discovery, and an ICMP Packet Too 1807 Big message MUST be sent by the encapsulating DR if it receives a packet 1808 that will not fit in the effective MTU of the tunnel. If the MTU 1809 between the DR and the RP results in the effective tunnel MTU being 1810 smaller than 1280 (the IPv6 minimum MTU), the DR MUST send Fragmentation 1811 Required messages with an MTU value of 1280 and MUST fragment its PIM 1812 register messages as required, using an IPv6 fragmentation header 1813 between the outer IPv6 header and the PIM Register header. 1815 The TTL of a forwarded data packet is decremented before it is 1816 encapsulated in the Register Tunnel. The encapsulating packet uses the 1817 normal TTL that the router would use for any locally-generated IP 1818 packet. 1820 The IP ECN bits should be copied from the original packet to the IP 1821 header of the encapsulating packet. They SHOULD NOT be set 1822 independently by the encapsulating router. 1824 The Diffserv Code Point (DSCP) should be copied from the original packet 1825 to the IP header of the encapsulating packet. It MAY be set 1826 independently by the encapsulating router, based upon static 1827 configuration or traffic classification. See [10] for more discussion 1828 on setting the DSCP on tunnels. 1830 Handling Register-Stop(*,G) Messages at the DR 1832 An old RP might send a Register-Stop message with the source address set 1833 to all-zeros. This was the normal course of action in RFC 2326 when the 1834 Register message matched against (*,G) state at the RP, and was defined 1835 as meaning "stop encapsulating all sources for this group". However, 1836 the behavior of such a Register-Stop(*,G) is ambiguous or incorrect in 1837 some circumstances. 1839 We specify that an RP should not send Register-Stop(*,G) messages, but 1840 for compatibility, a DR should be able to accept one if it is received. 1842 A Register-Stop(*,G) should be treated as a Register-Stop(S,G) for all 1843 (S,G) Register state machines that are not in the NoInfo state. A 1844 router should not apply a Register-Stop(*,G) to sources that become 1845 active after the Register-Stop(*,G) was received. 1847 4.4.2. Receiving Register Messages at the RP 1849 When an RP receives a Register message, the course of action is decided 1850 according to the following pseudocode: 1852 packet_arrives_on_rp_tunnel( pkt ) { 1853 if( outer.dst is not one of my addresses ) { 1854 drop the packet silently. 1855 # Note: this may be a spoofing attempt 1856 } 1857 if( I_am_RP(G) AND outer.dst == RP(G) ) { 1858 sentRegisterStop = FALSE; 1859 if ( register.borderbit == TRUE ) { 1860 if ( PMBR(S,G) == unknown ) { 1861 PMBR(S,G) = outer.src 1862 } else if ( outer.src != PMBR(S,G) ) { 1863 send Register-Stop(S,G) to outer.src 1864 drop the packet silently. 1865 } 1866 } 1867 if ( SPTbit(S,G) OR 1868 ( SwitchToSptDesired(S,G) AND ( inherited_olist(S,G) == NULL ))) { 1869 send Register-Stop(S,G) to outer.src 1870 sentRegisterStop = TRUE; 1871 } 1872 if ( SPTbit(S,G) OR SwitchToSptDesired(S,G) ) { 1873 if ( sentRegisterStop == TRUE ) { 1874 restart KeepaliveTimer(S,G) to RP_Keepalive_Period; 1875 } else { 1876 restart KeepaliveTimer(S,G) to Keepalive_Period; 1877 } 1878 } 1879 if( !SPTbit(S,G) AND ! pkt.NullRegisterBit ) { 1880 decapsulate and forward the inner packet to 1881 inherited_olist(S,G,rpt) # Note (+) 1882 } 1883 } else { 1884 send Register-Stop(S,G) to outer.src 1885 # Note (*) 1886 } 1887 } 1889 outer.dst is the IP destination address of the encapsulating header. 1891 outer.src is the IP source address of the encapsulating header, i.e., 1892 the DR's address. 1894 I_am_RP(G) is true if the group-to-RP mapping indicates that this router 1895 is the RP for the group. 1897 Note (*): This may block traffic from S for Register_Suppression_Time if 1898 the DR learned about a new group-to-RP mapping before the RP did. 1899 However, this doesn't matter unless we figure out some way for the 1900 RP to also accept (*,G) joins when it doesn't yet realize that it 1901 is about to become the RP for G. This will all get sorted out once 1902 the RP learns the new group-to-rp mapping. We decided to do 1903 nothing about this and just accept the fact that PIM may suffer 1904 interrupted (*,G) connectivity following an RP change. 1906 Note (+): Implementations are advised to not make this a special case, 1907 but to arrange that this path rejoin the normal packet forwarding 1908 path. All of the appropriate actions from the "On receipt of data 1909 from S to G on interface iif" pseudocode in Section 4.2 should be 1910 performed. 1912 KeepaliveTimer(S,G) is restarted at the RP when packets arrive on the 1913 proper tunnel interface and the RP desires to switch to the SPT or the 1914 SPTbit is already set. This may cause the upstream (S,G) state machine 1915 to trigger a join if the inherited_olist(S,G) is not NULL; 1917 An RP should preserve (S,G) state that was created in response to a 1918 Register message for at least ( 3 * Register_Suppression_Time ), 1919 otherwise the RP may stop joining (S,G) before the DR for S has 1920 restarted sending registers. Traffic would then be interrupted until 1921 the Register-Stop Timer expires at the DR. 1923 Thus, at the RP, KeepaliveTimer(S,G) should be restarted to ( 3 * 1924 Register_Suppression_Time + Register_Probe_Time ). 1926 When forwarding a packet from the Register Tunnel, the TTL of the 1927 original data packet is decremented after it is decapsulated. 1929 The IP ECN bits should be copied from the IP header of the Register 1930 packet to the decapsulated packet. 1932 The Diffserv Code Point (DSCP) should be copied from the IP header of 1933 the Register packet to the decapsulated packet. The RP MAY retain the 1934 DSCP of the inner packet, or re-classify the packet and apply a 1935 different DSCP. Scenarios where each of these might be useful are 1936 discussed in [10]. 1938 4.5. PIM Join/Prune Messages 1940 A PIM Join/Prune message consists of a list of groups and a list of 1941 Joined and Pruned sources for each group. When processing a received 1942 Join/Prune message, each Joined or Pruned source for a Group is 1943 effectively considered individually, and applies to one or more of the 1944 following state machines. When considering a Join/Prune message whose 1945 Upstream Neighbor Address field addresses this router, (*,G) Joins and 1946 Prunes can affect both the (*,G) and (S,G,rpt) downstream state 1947 machines, while (*,*,RP), (S,G) and (S,G,rpt) Joins and Prunes can only 1948 affect their respective downstream state machines. When considering a 1949 Join/Prune message whose Upstream Neighbor Address field addresses 1950 another router, most Join or Prune messages could affect each upstream 1951 state machine. 1953 In general, a PIM Join/Prune message should only be accepted for 1954 processing if it comes from a known PIM neighbor. A PIM router hears 1955 about PIM neighbors through PIM Hello messages. If a router receives a 1956 Join/Prune message from a particular IP source address and it has not 1957 seen a PIM Hello message from that source address, then the Join/Prune 1958 message SHOULD be discarded without further processing. In addition, if 1959 the Hello message from a neighbor was authenticated using IPsec AH (see 1960 Section 6.3) then all Join/Prune messages from that neighbor MUST also 1961 be authenticated using IPsec AH. 1963 We note that some older PIM implementations incorrectly fail to send 1964 Hello messages on point-to-point interfaces, so we also RECOMMEND that a 1965 configuration option be provided to allow interoperation with such older 1966 routers, but that this configuration option SHOULD NOT be enabled by 1967 default. 1969 4.5.1. Receiving (*,*,RP) Join/Prune Messages 1971 The per-interface state machine for receiving (*,*,RP) Join/Prune 1972 Messages is given below. There are three states: 1974 NoInfo (NI) 1975 The interface has no (*,*,RP) Join state and no timers 1976 running. 1978 Join (J) 1979 The interface has (*,*,RP) Join state which will cause the 1980 router to forward packets destined for any group handled by RP 1981 from this interface except if there is also (S,G,rpt) prune 1982 information (see Section 4.5.4) or the router lost an assert 1983 on this interface. 1985 Prune-Pending (PP) 1986 The router has received a Prune(*,*,RP) on this interface from 1987 a downstream neighbor and is waiting to see whether the prune 1988 will be overridden by another downstream router. For 1989 forwarding purposes, the Prune-Pending state functions exactly 1990 like the Join state. 1992 In addition, the state machine uses two timers: 1994 ExpiryTimer (ET) 1995 This timer is restarted when a valid Join(*,*,RP) is received. 1996 Expiry of the ExpiryTimer causes the interface state to revert 1997 to NoInfo for this RP. 1999 Prune-Pending Timer (PPT) 2000 This timer is set when a valid Prune(*,*,RP) is received. 2001 Expiry of the Prune-Pending Timer causes the interface state 2002 to revert to NoInfo for this RP. 2004 Figure 2: Downstream per-interface (*,*,RP) state machine in tabular form 2006 r+-------------++----------------------------------------------------------+ 2007 | || Event | 2008 | ++-------------+--------------+--------------+--------------+ 2009 |Prev State ||Receive | Receive | Prune- | Expiry Timer | 2010 | ||Join(*,*,RP) | Prune | Pending | Expires | 2011 | || | (*,*,RP) | Timer | | 2012 | || | | Expires | | 2013 |+-------------++-------------+--------------+--------------+--------------+ 2014 | ||-> J state | -> NI state | - | - | 2015 |NoInfo (NI) ||start Expiry | | | | 2016 | ||Timer | | | | 2017 |+-------------++-------------+--------------+--------------+--------------+ 2018 | ||-> J state | -> PP state | - | -> NI state | 2019 |Join (J) ||restart | start Prune- | | | 2020 | ||Expiry Timer | Pending | | | 2021 | || | Timer | | | 2022 |+-------------++-------------+--------------+--------------+--------------+ 2023 |Prune- ||-> J state | -> PP state | -> NI state | -> NI state | 2024 |Pending (PP) ||restart | | Send Prune- | | 2025 | ||Expiry Timer | | Echo(*,*,RP) | | 2026 |+-------------++-------------+--------------+--------------+--------------+ 2028 The transition events "Receive Join(*,*,RP)" and "Receive Prune(*,*,RP)" | 2029 imply receiving a Join or Prune targeted to this router's primary IP | 2030 address on the received interface. If the destination address is not 2031 correct, these state transitions in this state machine must not occur, 2032 although seeing such a packet may cause state transitions in other state 2033 machines. 2035 On unnumbered interfaces on point-to-point links, the router's address 2036 should be the same as the source address it chose for the Hello message 2037 it sent over that interface. However on point-to-point links we also 2038 recommend that for backwards compatibility PIM Join/Prune messages with 2039 a destination address of all zeros are also accepted. 2041 Transitions from NoInfo State 2043 When in NoInfo state, the following event may trigger a transition: 2045 Receive Join(*,*,RP) 2046 A Join(*,*,RP) is received on interface I with its Upstream 2047 Neighbor Address set to the router's primary IP address on I. | 2049 The (*,*,RP) downstream state machine on interface I 2050 transitions to the Join state. The Expiry Timer (ET) is 2051 started, and set to the HoldTime from the triggering 2052 Join/Prune message. 2054 Note that it is possible to receive a Join(*,*,RP) message for 2055 an RP that we do not have information telling us that it is an 2056 RP. In the case of (*,*,RP) state, so long as we have a route 2057 to the RP, this will not cause a problem, and the transition 2058 should still take place. 2060 Transitions from Join State 2062 When in Join state, the following events may trigger a transition: 2064 Receive Join(*,*,RP) 2065 A Join(*,*,RP) is received on interface I with its Upstream 2066 Neighbor Address set to the router's primary IP address on I. | 2068 The (*,*,RP) downstream state machine on interface I remains 2069 in Join state, and the Expiry Timer (ET) is restarted, set to 2070 maximum of its current value and the HoldTime from the 2071 triggering Join/Prune message. 2073 Receive Prune(*,*,RP) 2074 A Prune(*,*,RP) is received on interface I with its Upstream 2075 Neighbor Address set to the router's primary IP address on I. | 2077 The (*,*,RP) downstream state machine on interface I 2078 transitions to the Prune-Pending state. The Prune-Pending 2079 Timer is started; it is set to the J/P_Override_Interval(I) if 2080 the router has more than one neighbor on that interface; 2081 otherwise it is set to zero causing it to expire immediately. 2083 Expiry Timer Expires 2084 The Expiry Timer for the (*,*,RP) downstream state machine on 2085 interface I expires. 2087 The (*,*,RP) downstream state machine on interface I 2088 transitions to the NoInfo state. 2090 Transitions from Prune-Pending State 2092 When in Prune-Pending state, the following events may trigger a 2093 transition: 2095 Receive Join(*,*,RP) 2096 A Join(*,*,RP) is received on interface I with its Upstream 2097 Neighbor Address set to the router's primary IP address on I. | 2099 The (*,*,RP) downstream state machine on interface I 2100 transitions to the Join state. The Prune-Pending Timer is 2101 canceled (without triggering an expiry event). The Expiry 2102 Timer is restarted, set to maximum of its current value and 2103 the HoldTime from the triggering Join/Prune message. 2105 Expiry Timer Expires 2106 The Expiry Timer for the (*,*,RP) downstream state machine on 2107 interface I expires. 2109 The (*,*,RP) downstream state machine on interface I 2110 transitions to the NoInfo state. 2112 Prune-Pending Timer Expires 2113 The Prune-Pending Timer for the (*,*,RP) downstream state 2114 machine on interface I expires. 2116 The (*,*,RP) downstream state machine on interface I 2117 transitions to the NoInfo state. A PruneEcho(*,*,RP) is sent 2118 onto the subnet connected to interface I. 2120 The action "Send PruneEcho(*,*,RP)" is triggered when the 2121 router stops forwarding on an interface as a result of a 2122 prune. A PruneEcho(*,*,RP) is simply a Prune(*,*,RP) message 2123 sent by the upstream router on a LAN with its own address in 2124 the Upstream Neighbor Address field. Its purpose is to add 2125 additional reliability so that if a Prune that should have 2126 been overridden by another router is lost locally on the LAN, 2127 then the PruneEcho may be received and cause the override to 2128 happen. A PruneEcho(*,*,RP) need not be sent on an interface 2129 that contains only a single PIM neighbor during the time this 2130 state machine was in Prune-Pending state. 2132 4.5.2. Receiving (*,G) Join/Prune Messages 2134 When a router receives a Join(*,G) or Prune(*,G) it must first check to 2135 see whether the RP in the message matches RP(G) (the router's idea of 2136 who the RP is). If the RP in the message does not match RP(G) the 2137 Join(*,G) or Prune(*,G) should be silently dropped. (Note that other 2138 source list entries such as (S,G,rpt) or (S,G) in the same Group 2139 Specific Set should still be processed.) If a router has no RP 2140 information (e.g. has not recently received a BSR message) then it may 2141 choose to accept Join(*,G) or Prune(*,G) and treat the RP in the message 2142 as RP(G). 2144 The per-interface state machine for receiving (*,G) Join/Prune Messages 2145 is given below. There are three states: 2147 NoInfo (NI) 2148 The interface has no (*,G) Join state and no timers running. 2150 Join (J) 2151 The interface has (*,G) Join state which will cause the router 2152 to forward packets destined for G from this interface except 2153 if there is also (S,G,rpt) prune information (see Section 2154 4.5.4) or the router lost an assert on this interface. 2156 Prune-Pending (PP) 2157 The router has received a Prune(*,G) on this interface from a 2158 downstream neighbor and is waiting to see whether the prune 2159 will be overridden by another downstream router. For 2160 forwarding purposes, the Prune-Pending state functions exactly 2161 like the Join state. 2163 In addition, the state machine uses two timers: 2165 Expiry Timer (ET) 2166 This timer is restarted when a valid Join(*,G) is received. 2167 Expiry of the Expiry Timer causes the interface state to 2168 revert to NoInfo for this group. 2170 Prune-Pending Timer (PPT) 2171 This timer is set when a valid Prune(*,G) is received. Expiry 2172 of the Prune-Pending Timer causes the interface state to 2173 revert to NoInfo for this group. 2175 Figure 3: Downstream per-interface (*,G) state machine in tabular form 2177 i+-------------++---------------------------------------------------------+ 2178 | || Event | 2179 | ++-------------+--------------+-------------+--------------+ 2180 |Prev State ||Receive | Receive | Prune- | Expiry Timer | 2181 | ||Join(*,G) | Prune(*,G) | Pending | Expires | 2182 | || | | Timer | | 2183 | || | | Expires | | 2184 | 2185 +-------------++-------------+--------------+-------------+--------------+ 2186 | ||-> J state | -> NI state | - | - | 2187 |NoInfo (NI) ||start Expiry | | | | 2188 | ||Timer | | | | 2189 | 2190 +-------------++-------------+--------------+-------------+--------------+ 2191 | ||-> J state | -> PP state | - | -> NI state | 2192 |Join (J) ||restart | start Prune- | | | 2193 | ||Expiry Timer | Pending | | | 2194 | || | Timer | | | 2195 | 2196 +-------------++-------------+--------------+-------------+--------------+ 2197 |Prune- ||-> J state | -> PP state | -> NI state | -> NI state | 2198 |Pending (PP) ||restart | | Send Prune- | | 2199 | ||Expiry Timer | | Echo(*,G) | | 2200 | 2201 +-------------++-------------+--------------+-------------+--------------+ 2203 The transition events "Receive Join(*,G)" and "Receive Prune(*,G)" imply | 2204 receiving a Join or Prune targeted to this router's primary IP address | 2205 on the received interface. If the destination address is not correct, 2206 these state transitions in this state machine must not occur, although 2207 seeing such a packet may cause state transitions in other state 2208 machines. 2210 On unnumbered interfaces on point-to-point links, the router's address 2211 should be the same as the source address it chose for the Hello message 2212 it sent over that interface. However on point-to-point links we also 2213 recommend that for backwards compatibility PIM Join/Prune messages with 2214 a destination address of all zeros are also accepted. 2216 Transitions from NoInfo State 2218 When in NoInfo state, the following event may trigger a transition: 2220 Receive Join(*,G) 2221 A Join(*,G) is received on interface I with its Upstream 2222 Neighbor Address set to the router's primary IP address on I. | 2224 The (*,G) downstream state machine on interface I transitions 2225 to the Join state. The Expiry Timer (ET) is started, and set 2226 to the HoldTime from the triggering Join/Prune message. 2228 Transitions from Join State 2230 When in Join state, the following events may trigger a transition: 2232 Receive Join(*,G) 2233 A Join(*,G) is received on interface I with its Upstream 2234 Neighbor Address set to the router's primary IP address on I. | 2236 The (*,G) downstream state machine on interface I remains in 2237 Join state, and the Expiry Timer (ET) is restarted, set to 2238 maximum of its current value and the HoldTime from the 2239 triggering Join/Prune message. 2241 Receive Prune(*,G) 2242 A Prune(*,G) is received on interface I with its Upstream 2243 Neighbor Address set to the router's primary IP address on I. | 2245 The (*,G) downstream state machine on interface I transitions 2246 to the Prune-Pending state. The Prune-Pending Timer is 2247 started; it is set to the J/P_Override_Interval(I) if the 2248 router has more than one neighbor on that interface; otherwise 2249 it is set to zero causing it to expire immediately. 2251 Expiry Timer Expires 2252 The Expiry Timer for the (*,G) downstream state machine on 2253 interface I expires. 2255 The (*,G) downstream state machine on interface I transitions 2256 to the NoInfo state. 2258 Transitions from Prune-Pending State 2260 When in Prune-Pending state, the following events may trigger a 2261 transition: 2263 Receive Join(*,G) 2264 A Join(*,G) is received on interface I with its Upstream 2265 Neighbor Address set to the router's primary IP address on I. | 2267 The (*,G) downstream state machine on interface I transitions 2268 to the Join state. The Prune-Pending Timer is canceled 2269 (without triggering an expiry event). The Expiry Timer is 2270 restarted, set to maximum of its current value and the 2271 HoldTime from the triggering Join/Prune message. 2273 Expiry Timer Expires 2274 The Expiry Timer for the (*,G) downstream state machine on 2275 interface I expires. 2277 The (*,G) downstream state machine on interface I transitions 2278 to the NoInfo state. 2280 Prune-Pending Timer Expires 2281 The Prune-Pending Timer for the (*,G) downstream state machine 2282 on interface I expires. 2284 The (*,G) downstream state machine on interface I transitions 2285 to the NoInfo state. A PruneEcho(*,G) is sent onto the subnet 2286 connected to interface I. 2288 The action "Send PruneEcho(*,G)" is triggered when the router 2289 stops forwarding on an interface as a result of a prune. A 2290 PruneEcho(*,G) is simply a Prune(*,G) message sent by the 2291 upstream router on a LAN with its own address in the Upstream 2292 Neighbor Address field. Its purpose is to add additional 2293 reliability so that if a Prune that should have been 2294 overridden by another router is lost locally on the LAN, then 2295 the PruneEcho may be received and cause the override to 2296 happen. A PruneEcho(*,G) need not be sent on an interface 2297 that contains only a single PIM neighbor during the time this 2298 state machine was in Prune-Pending state. 2300 4.5.3. Receiving (S,G) Join/Prune Messages 2302 The per-interface state machine for receiving (S,G) Join/Prune messages 2303 is given below, and is almost identical to that for (*,G) messages. 2304 There are three states: 2306 NoInfo (NI) 2307 The interface has no (S,G) Join state and no (S,G) timers 2308 running. 2310 Join (J) 2311 The interface has (S,G) Join state which will cause the router 2312 to forward packets from S destined for G from this interface 2313 if the (S,G) state is active (the SPTbit is set) except if the 2314 router lost an assert on this interface. 2316 Prune-Pending (PP) 2317 The router has received a Prune(S,G) on this interface from a 2318 downstream neighbor and is waiting to see whether the prune 2319 will be overridden by another downstream router. For 2320 forwarding purposes, the Prune-Pending state functions exactly 2321 like the Join state. 2323 In addition, there are two timers: 2325 Expiry Timer (ET) 2326 This timer is set when a valid Join(S,G) is received. Expiry 2327 of the Expiry Timer causes this state machine to revert to 2328 NoInfo state. 2330 Prune-Pending Timer (PPT) 2331 This timer is set when a valid Prune(S,G) is received. Expiry 2332 of the Prune-Pending Timer causes this state machine to revert 2333 to NoInfo state. 2335 Figure 4: Downstream per-interface (S,G) state machine in tabular form 2337 i+-------------++---------------------------------------------------------+ 2338 | || Event | 2339 | ++-------------+--------------+-------------+--------------+ 2340 |Prev State ||Receive | Receive | Prune- | Expiry Timer | 2341 | ||Join(S,G) | Prune(S,G) | Pending | Expires | 2342 | || | | Timer | | 2343 | || | | Expires | | 2344 | 2345 +-------------++-------------+--------------+-------------+--------------+ 2346 | ||-> J state | -> NI state | - | - | 2347 |NoInfo (NI) ||start Expiry | | | | 2348 | ||Timer | | | | 2349 | 2350 +-------------++-------------+--------------+-------------+--------------+ 2351 | ||-> J state | -> PP state | - | -> NI state | 2352 |Join (J) ||restart | start Prune- | | | 2353 | ||Expiry Timer | Pending | | | 2354 | || | Timer | | | 2355 | 2356 +-------------++-------------+--------------+-------------+--------------+ 2357 |Prune- ||-> J state | -> PP state | -> NI state | -> NI state | 2358 |Pending (PP) ||restart | | Send Prune- | | 2359 | ||Expiry Timer | | Echo(S,G) | | 2360 | 2361 +-------------++-------------+--------------+-------------+--------------+ 2363 The transition events "Receive Join(S,G)" and "Receive Prune(S,G)" imply | 2364 receiving a Join or Prune targeted to this router's primary IP address | 2365 on the received interface. If the destination address is not correct, 2366 these state transitions in this state machine must not occur, although 2367 seeing such a packet may cause state transitions in other state 2368 machines. 2370 On unnumbered interfaces on point-to-point links, the router's address 2371 should be the same as the source address it chose for the Hello message 2372 it sent over that interface. However on point-to-point links we also 2373 recommend that for backwards compatibility PIM Join/Prune messages with 2374 a destination address of all zeros are also accepted. 2376 Transitions from NoInfo State 2378 When in NoInfo state, the following event may trigger a transition: 2380 Receive Join(S,G) 2381 A Join(S,G) is received on interface I with its Upstream 2382 Neighbor Address set to the router's primary IP address on I. | 2384 The (S,G) downstream state machine on interface I transitions 2385 to the Join state. The Expiry Timer (ET) is started, and set 2386 to the HoldTime from the triggering Join/Prune message. 2388 Transitions from Join State 2390 When in Join state, the following events may trigger a transition: 2392 Receive Join(S,G) 2393 A Join(S,G) is received on interface I with its Upstream 2394 Neighbor Address set to the router's primary IP address on I. | 2396 The (S,G) downstream state machine on interface I remains in 2397 Join state, and the Expiry Timer (ET) is restarted, set to 2398 maximum of its current value and the HoldTime from the 2399 triggering Join/Prune message. 2401 Receive Prune(S,G) 2402 A Prune(S,G) is received on interface I with its Upstream 2403 Neighbor Address set to the router's primary IP address on I. | 2405 The (S,G) downstream state machine on interface I transitions 2406 to the Prune-Pending state. The Prune-Pending Timer is 2407 started; it is set to the J/P_Override_Interval(I) if the 2408 router has more than one neighbor on that interface; otherwise 2409 it is set to zero causing it to expire immediately. 2411 Expiry Timer Expires 2412 The Expiry Timer for the (S,G) downstream state machine on 2413 interface I expires. 2415 The (S,G) downstream state machine on interface I transitions 2416 to the NoInfo state. 2418 Transitions from Prune-Pending State 2420 When in Prune-Pending state, the following events may trigger a 2421 transition: 2423 Receive Join(S,G) 2424 A Join(S,G) is received on interface I with its Upstream 2425 Neighbor Address set to the router's primary IP address on I. | 2427 The (S,G) downstream state machine on interface I transitions 2428 to the Join state. The Prune-Pending Timer is canceled 2429 (without triggering an expiry event). The Expiry Timer is 2430 restarted, set to maximum of its current value and the 2431 HoldTime from the triggering Join/Prune message. 2433 Expiry Timer Expires 2434 The Expiry Timer for the (S,G) downstream state machine on 2435 interface I expires. 2437 The (S,G) downstream state machine on interface I transitions 2438 to the NoInfo state. 2440 Prune-Pending Timer Expires 2441 The Prune-Pending Timer for the (S,G) downstream state machine 2442 on interface I expires. 2444 The (S,G) downstream state machine on interface I transitions 2445 to the NoInfo state. A PruneEcho(S,G) is sent onto the subnet 2446 connected to interface I. 2448 The action "Send PruneEcho(S,G)" is triggered when the router 2449 stops forwarding on an interface as a result of a prune. A 2450 PruneEcho(S,G) is simply a Prune(S,G) message sent by the 2451 upstream router on a LAN with its own address in the Upstream 2452 Neighbor Address field. Its purpose is to add additional 2453 reliability so that if a Prune that should have been 2454 overridden by another router is lost locally on the LAN, then 2455 the PruneEcho may be received and cause the override to 2456 happen. A PruneEcho(S,G) need not be sent on an interface 2457 that contains only a single PIM neighbor during the time this 2458 state machine was in Prune-Pending state. 2460 4.5.4. Receiving (S,G,rpt) Join/Prune Messages 2462 The per-interface state machine for receiving (S,G,rpt) Join/Prune 2463 messages is given below. There are five states: 2465 NoInfo (NI) 2466 The interface has no (S,G,rpt) Prune state and no (S,G,rpt) 2467 timers running. 2469 Prune (P) 2470 The interface has (S,G,rpt) Prune state which will cause the 2471 router not to forward packets from S destined for G from this 2472 interface even though the interface has active (*,G) Join 2473 state. 2475 Prune-Pending (PP) 2476 The router has received a Prune(S,G,rpt) on this interface 2477 from a downstream neighbor and is waiting to see whether the 2478 prune will be overridden by another downstream router. For 2479 forwarding purposes, the Prune-Pending state functions exactly 2480 like the NoInfo state. 2482 PruneTmp (P') 2483 This state is a transient state which for forwarding purposes 2484 behaves exactly like the Prune state. A (*,G) Join has been 2485 received (which may cancel the (S,G,rpt) Prune). As we parse 2486 the Join/Prune message from top to bottom, we first enter this 2487 state if the message contains a (*,G) Join. Later in the 2488 message we will normally encounter an (S,G,rpt) prune to re- 2489 instate the Prune state. However if we reach the end of the 2490 message without encountering such a (S,G,rpt) prune, then we 2491 will revert to NoInfo state in this state machine. 2493 As no time is spent in this state, no timers can expire. 2495 Prune-Pending-Tmp (PP') 2496 This state is a transient state which is identical to P' 2497 except that it is associated with the PP state rather than the 2498 P state. For forwarding purposes, PP' behaves exactly like PP 2499 state. 2501 In addition, there are two timers: 2503 Expiry Timer (ET) 2504 This timer is set when a valid Prune(S,G,rpt) is received. 2505 Expiry of the Expiry Timer causes this state machine to revert 2506 to NoInfo state. 2508 Prune-Pending Timer (PPT) 2509 This timer is set when a valid Prune(S,G,rpt) is received. 2510 Expiry of the Prune-Pending Timer causes this state machine to 2511 move on to Prune state. 2513 Figure 5: Downstream per-interface (S,G,rpt) state machine in tabular form 2515 r+----------++----------------------------------------------------------------+ 2516 | || Event | 2517 | ++----------+-----------+-----------+---------+---------+---------+ 2518 |Prev ||Receive | Receive | Receive | End of | Prune- | Expiry | 2519 |State ||Join(*,G) | Join | Prune | Message | Pending | Timer | 2520 | || | (S,G,rpt) | (S,G,rpt) | | Timer | Expires | 2521 | || | | | | Expires | | 2522 +----------++----------+-----------+-----------+---------+---------+---------+ 2523 | ||- | - | -> PP | - | - | - | 2524 | || | | state | | | | 2525 | || | | start | | | | 2526 |NoInfo || | | Prune- | | | | 2527 |(NI) || | | Pending | | | | 2528 | || | | Timer; | | | | 2529 | || | | start | | | | 2530 | || | | Expiry | | | | 2531 | || | | Timer | | | | 2532 +----------++----------+-----------+-----------+---------+---------+---------+ 2533 | ||-> P' | -> NI | -> P | - | - | -> NI | 2534 | ||state | state | state | | | state | 2535 |Prune (P) || | | restart | | | | 2536 | || | | Expiry | | | | 2537 | || | | Timer | | | | 2538 +----------++----------+-----------+-----------+---------+---------+---------+ 2539 |Prune- ||-> PP' | -> NI | - | - | -> P | - | 2540 |Pending ||state | state | | | state | | 2541 |(PP) || | | | | | | 2542 +----------++----------+-----------+-----------+---------+---------+---------+ 2543 | ||- | - | -> P | -> NI | - | - | 2544 |Prune-Tmp || | | state | state | | | 2545 |(P') || | | restart | | | | 2546 | || | | Expiry | | | | 2547 | || | | Timer | | | | 2548 +----------++----------+-----------+-----------+---------+---------+---------+ 2549 | ||- | - | -> PP | -> NI | - | - | 2550 |Prune- || | | state | state | | | 2551 |Pending- || | | restart | | | | 2552 |Tmp (PP') || | | Expiry | | | | 2553 | || | | Timer | | | | 2554 +----------++----------+-----------+-----------+---------+---------+---------+ 2556 The transition events "Receive Join(S,G,rpt)", "Receive Prune(S,G,rpt)", 2557 and "Receive Join(*,G)" imply receiving a Join or Prune targeted to this | 2558 router's primary IP address on the received interface. If the 2559 destination address is not correct, these state transitions in this 2560 state machine must not occur, although seeing such a packet may cause 2561 state transitions in other state machines. 2563 On unnumbered interfaces on point-to-point links, the router's address 2564 should be the same as the source address it chose for the Hello message 2565 it sent over that interface. However on point-to-point links we also 2566 recommend that PIM Join/Prune messages with a destination address of all 2567 zeros are also accepted. 2569 Transitions from NoInfo State 2571 When in NoInfo (NI) state, the following event may trigger a transition: 2573 Receive Prune(S,G,rpt) 2574 A Prune(S,G,rpt) is received on interface I with its Upstream 2575 Neighbor Address set to the router's primary IP address on I. | 2577 The (S,G,rpt) downstream state machine on interface I 2578 transitions to the Prune-Pending state. The Expiry Timer (ET) 2579 is started, and set to the HoldTime from the triggering 2580 Join/Prune message. The Prune-Pending Timer is started; it is 2581 set to the J/P_Override_Interval(I) if the router has more 2582 than one neighbor on that interface; otherwise it is set to 2583 zero causing it to expire immediately. 2585 Transitions from Prune-Pending State 2587 When in Prune-Pending (PP) state, the following events may trigger a 2588 transition: 2590 Receive Join(*,G) 2591 A Join(*,G) is received on interface I with its Upstream | 2592 Neighbor Address set to the router's primary IP address on I. 2594 The (S,G,rpt) downstream state machine on interface I 2595 transitions to Prune-Pending-Tmp state whilst the remainder of 2596 the compound Join/Prune message containing the Join(*,G) is 2597 processed. 2599 Receive Join(S,G,rpt) 2600 A Join(S,G,rpt) is received on interface I with its Upstream 2601 Neighbor Address set to the router's primary IP address on I. | 2603 The (S,G,rpt) downstream state machine on interface I 2604 transitions to NoInfo state. ET and PPT are canceled. 2606 Prune-Pending Timer Expires 2607 The Prune-Pending Timer for the (S,G,rpt) downstream state 2608 machine on interface I expires. 2610 The (S,G,rpt) downstream state machine on interface I 2611 transitions to the Prune state. 2613 Transitions from Prune State 2615 When in Prune (P) state, the following events may trigger a transition: 2617 Receive Join(*,G) 2618 A Join(*,G) is received on interface I with its Upstream 2619 Neighbor Address set to the router's primary IP address on I. | 2621 The (S,G,rpt) downstream state machine on interface I 2622 transitions to PruneTmp state whilst the remainder of the 2623 compound Join/Prune message containing the Join(*,G) is 2624 processed. 2626 Receive Join(S,G,rpt) 2627 A Join(S,G,rpt) is received on interface I with its Upstream 2628 Neighbor Address set to the router's primary IP address on I. | 2630 The (S,G,rpt) downstream state machine on interface I 2631 transitions to NoInfo state. ET and PPT are canceled. 2633 Receive Prune(S,G,rpt) 2634 A Prune(S,G,rpt) is received on interface I with its Upstream 2635 Neighbor Address set to the router's primary IP address on I. | 2637 The (S,G,rpt) downstream state machine on interface I remains 2638 in Prune state. The Expiry Timer (ET) is restarted, set to 2639 maximum of its current value and the HoldTime from the 2640 triggering Join/Prune message. 2642 Expiry Timer Expires 2643 The Expiry Timer for the (S,G,rpt) downstream state machine on 2644 interface I expires. 2646 The (S,G,rpt) downstream state machine on interface I 2647 transitions to the NoInfo state. 2649 Transitions from Prune-Pending-Tmp State 2651 When in Prune-Pending-Tmp (PP') state and processing a compound 2652 Join/Prune message, the following events may trigger a transition: 2654 Receive Prune(S,G,rpt) 2655 The compound Join/Prune message contains a Prune(S,G,rpt). 2657 The (S,G,rpt) downstream state machine on interface I 2658 transitions back to the Prune-Pending state. The Expiry Timer 2659 (ET) is restarted, set to maximum of its current value and the 2660 HoldTime from the triggering Join/Prune message. 2662 End of Message 2663 The end of the compound Join/Prune message is reached. 2665 The (S,G,rpt) downstream state machine on interface I 2666 transitions to the NoInfo state. ET and PPT are canceled. 2668 Transitions from PruneTmp State 2670 When in PruneTmp (P') state and processing a compound Join/Prune 2671 message, the following events may trigger a transition: 2673 Receive Prune(S,G,rpt) 2674 The compound Join/Prune message contains a Prune(S,G,rpt). 2676 The (S,G,rpt) downstream state machine on interface I 2677 transitions back to the Prune state. The Expiry Timer (ET) is 2678 restarted, set to maximum of its current value and the 2679 HoldTime from the triggering Join/Prune message. 2681 End of Message 2682 The end of the compound Join/Prune message is reached. 2684 The (S,G,rpt) downstream state machine on interface I 2685 transitions to the NoInfo state. ET is canceled. 2687 Notes: 2689 Receiving a Prune(*,G) does not affect the (S,G,rpt) downstream state 2690 machine. 2692 Receiving a Join(*,*,RP) does not affect the (S,G,rpt) downstream state 2693 machine. If a router has originated Join(*,*,RP) and pruned a source 2694 off it using Prune(S,G,rpt), then to receive that source again it should 2695 explicitly re-join using Join(S,G,rpt) or Join(*,G). In some LAN 2696 topologies it is possible for a router sending a new Join(*,*,RP) to 2697 have to wait as much as a Join/Prune Interval before noticing that it 2698 needs to override a neighbor's pre-existing Prune(S,G,rpt). This is 2699 considered acceptable, as (*,*,RP) state is intended to be used only in 2700 long-lived and persistent scenarios. 2702 4.5.5. Sending (*,*,RP) Join/Prune Messages 2704 The per-interface state machines for (*,*,RP) hold join state from 2705 downstream PIM routers. This state then determines whether a router 2706 needs to propagate a Join(*,*,RP) upstream towards the RP. 2708 If a router wishes to propagate a Join(*,*,RP) upstream, it must also 2709 watch for messages on its upstream interface from other routers on that 2710 subnet, and these may modify its behavior. If it sees a Join(*,*,RP) to 2711 the correct upstream neighbor, it should suppress its own Join(*,*,RP). 2712 If it sees a Prune(*,*,RP) to the correct upstream neighbor, it should 2713 be prepared to override that prune by sending a Join(*,*,RP) almost 2714 immediately. Finally, if it sees the Generation ID (see Section 4.3) of 2715 the correct upstream neighbor change, it knows that the upstream 2716 neighbor has lost state, and it should be prepared to refresh the state 2717 by sending a Join(*,*,RP) almost immediately. 2719 In addition, if the MRIB changes to indicate that the next hop towards 2720 the RP has changed, the router should prune off from the old next hop, 2721 and join towards the new next hop. 2723 The upstream (*,*,RP) state machine contains only two states: 2725 Not Joined 2726 The downstream state machines and local membership information do 2727 not indicate that the router needs to join the (*,*,RP) tree for 2728 this RP. 2730 Joined 2731 The downstream state machines and local membership information 2732 indicate that the router should join the (*,*,RP) tree for this RP. 2734 In addition, one timer JT(*,*,RP) is kept which is used to trigger the 2735 sending of a Join(*,*,RP) to the upstream next hop towards the RP, 2736 NBR(RPF_interface(RP), MRIB.next_hop(RP)). 2738 Figure 6: Upstream (*,*,RP) state machine in tabular form 2740 +--------------------++-------------------------------------------------+ 2741 | || Event | 2742 | Prev State ++-------------------------+-----------------------+ 2743 | || JoinDesired | JoinDesired | 2744 | || (*,*,RP) ->True | (*,*,RP) ->False | 2745 | 2746 +--------------------++-------------------------+-----------------------+ 2747 | || -> J state | - | 2748 | NotJoined (NJ) || Send Join(*,*,RP); | | 2749 | || Set Join Timer to | | 2750 | || t_periodic | | 2751 | 2752 +--------------------++-------------------------+-----------------------+ 2753 | Joined (J) || - | -> NJ state | 2754 | || | Send Prune | 2755 | || | (*,*,RP); Cancel | 2756 | || | Join Timer | 2757 | 2758 +--------------------++-------------------------+-----------------------+ 2760 In addition, we have the following transitions which occur within the 2761 Joined state: 2763 i+-----------------------------------------------------------------------+ 2764 | In Joined (J) State | 2765 | 2766 +-------------------+--------------------+------------------------------+ 2767 | Timer Expires | See | See | 2768 | | Join(*,*,RP) | Prune(*,*,RP) | 2769 | | to MRIB. | to MRIB. | 2770 | | next_hop(RP) | next_hop(RP) | 2771 | 2772 +-------------------+--------------------+------------------------------+ 2773 | Send | Increase Join | Decrease Join | 2774 | Join(*,*,RP); | Timer to | Timer to | 2775 | Set Join Timer | t_joinsuppress | t_override | 2776 | to t_periodic | | | 2777 | 2778 +-------------------+--------------------+------------------------------+ 2779 T+-----------------------------------------------------------------------+ 2780 | In Joined (J) State | 2781 | 2782 +-----------------------------------+-----------------------------------+ 2783 | NBR(RPF_interface(RP), | MRIB.next_hop(RP) GenID | 2784 | MRIB.next_hop(RP)) | changes | 2785 | changes | | 2786 | 2787 +-----------------------------------+-----------------------------------+ 2788 | Send Join(*,*,RP) to new | Decrease Join Timer to | 2789 | next hop; Send | t_override | 2790 | Prune(*,*,RP) to old | | 2791 | next hop; set Join Timer | | 2792 | to t_periodic | | 2793 | 2794 +-----------------------------------+-----------------------------------+ 2796 This state machine uses the following macro: 2798 bool JoinDesired(*,*,RP) { 2799 if immediate_olist(*,*,RP) != NULL 2800 return TRUE 2801 else 2802 return FALSE 2803 } 2805 JoinDesired(*,*,RP) is true when the router has received (*,*,RP) Joins 2806 from any downstream interface. Note that although JoinDesired is true, 2807 the router's sending of a Join(*,*,RP) message may be suppressed by 2808 another router sending a Join(*,*,RP) onto the upstream interface. 2810 Transitions from NotJoined State 2812 When the upstream (*,*,RP) state machine is in NotJoined state, the 2813 following event may trigger a state transition: 2815 JoinDesired(*,*,RP) becomes True 2816 The downstream state for (*,*,RP) has changed so that at least 2817 one interface is in immediate_olist(*,*,RP), making 2818 JoinDesired(*,*,RP) become True. 2820 The upstream (*,*,RP) state machine transitions to Joined 2821 state. Send Join(*,*,RP) to the appropriate upstream 2822 neighbor, which is NBR(RPF_interface(RP), MRIB.next_hop(RP)). 2823 Set the Join Timer (JT) to expire after t_periodic seconds. 2825 Transitions from Joined State 2827 When the upstream (*,*,RP) state machine is in Joined state, the 2828 following events may trigger state transitions: 2830 JoinDesired(*,*,RP) becomes False 2831 The downstream state for (*,*,RP) has changed so no interface 2832 is in immediate_olist(*,*,RP), making JoinDesired(*,*,RP) 2833 become False. 2835 The upstream (*,*,RP) state machine transitions to NotJoined 2836 state. Send Prune(*,*,RP) to the appropriate upstream 2837 neighbor, which is NBR(RPF_interface(RP), MRIB.next_hop(RP)). 2838 Cancel the Join Timer (JT). 2840 Join Timer Expires 2841 The Join Timer (JT) expires, indicating time to send a 2842 Join(*,*,RP) 2844 Send Join(*,*,RP) to the appropriate upstream neighbor, which 2845 is NBR(RPF_interface(RP), MRIB.next_hop(RP)). Restart the 2846 Join Timer (JT) to expire after t_periodic seconds. 2848 See Join(*,*,RP) to MRIB.next_hop(RP) 2849 This event is only relevant if RPF_interface(RP) is a shared 2850 medium. This router sees another router on RPF_interface(RP) 2851 send a Join(*,*,RP) to NBR(RPF_interface(RP), | 2852 MRIB.next_hop(RP)). This causes this router to suppress its 2853 own Join. 2855 The upstream (*,*,RP) state machine remains in Joined state. 2857 Let t_joinsuppress be the minimum of t_suppressed and the 2858 HoldTime from the Join/Prune message triggering this event. 2859 If the Join Timer is set to expire in less than t_joinsuppress 2860 seconds, reset it so that it expires after t_joinsuppress 2861 seconds. If the Join Timer is set to expire in more than 2862 t_joinsuppress seconds, leave it unchanged. 2864 See Prune(*,*,RP) to MRIB.next_hop(RP) 2865 This event is only relevant if RPF_interface(RP) is a shared 2866 medium. This router sees another router on RPF_interface(RP) 2867 send a Prune(*,*,RP) to NBR(RPF_interface(RP), | 2868 MRIB.next_hop(RP)). As this router is in Joined state, it 2869 must override the Prune after a short random interval. 2871 The upstream (*,*,RP) state machine remains in Joined state. 2872 If the Join Timer is set to expire in more than t_override 2873 seconds, reset it so that it expires after t_override seconds. 2874 If the Join Timer is set to expire in less than t_override 2875 seconds, leave it unchanged. 2877 NBR(RPF_interface(RP), MRIB.next_hop(RP)) changes 2878 A change in the MRIB routing base causes the next hop towards 2879 the RP to change. 2881 The upstream (*,*,RP) state machine remains in Joined state. 2882 Send Join(*,*,RP) to the new upstream neighbor which is the 2883 new value of NBR(RPF_interface(RP), MRIB.next_hop(RP)). Send 2884 Prune(*,*,RP) to the old upstream neighbor, which is the old 2885 value of NBR(RPF_interface(RP), MRIB.next_hop(RP)). Set the 2886 Join Timer (JT) to expire after t_periodic seconds. 2888 MRIB.next_hop(RP) GenID changes 2889 The Generation ID of the router that is MRIB.next_hop(RP) 2890 changes. This normally means that this neighbor has lost 2891 state, and so the state must be refreshed. 2893 The upstream (*,*,RP) state machine remains in Joined state. 2894 If the Join Timer is set to expire in more than t_override 2895 seconds, reset it so that it expires after t_override seconds. 2897 4.5.6. Sending (*,G) Join/Prune Messages 2899 The per-interface state machines for (*,G) hold join state from 2900 downstream PIM routers. This state then determines whether a router 2901 needs to propagate a Join(*,G) upstream towards the RP. 2903 If a router wishes to propagate a Join(*,G) upstream, it must also watch 2904 for messages on its upstream interface from other routers on that 2905 subnet, and these may modify its behavior. If it sees a Join(*,G) to 2906 the correct upstream neighbor, it should suppress its own Join(*,G). If 2907 it sees a Prune(*,G) to the correct upstream neighbor, it should be 2908 prepared to override that prune by sending a Join(*,G) almost 2909 immediately. Finally, if it sees the Generation ID (see Section 4.3) of 2910 the correct upstream neighbor change, it knows that the upstream 2911 neighbor has lost state, and it should be prepared to refresh the state 2912 by sending a Join(*,G) almost immediately. 2914 If a (*,G) Assert occurs on the upstream interface, and this changes 2915 this router's idea of the upstream neighbor, it should be prepared to 2916 ensure that the Assert winner is aware of downstream routers by sending 2917 a Join(*,G) almost immediately. 2919 In addition, if the MRIB changes to indicate that the next hop towards 2920 the RP has changed, and either the upstream interface changes or there 2921 is no Assert winner on the upstream interface, the router should prune 2922 off from the old next hop, and join towards the new next hop. 2924 The upstream (*,G) state machine only contains two states: 2926 Not Joined 2927 The downstream state machines indicate that the router does not 2928 need to join the RP tree for this group. 2930 Joined 2931 The downstream state machines indicate that the router should join 2932 the RP tree for this group. 2934 In addition, one timer JT(*,G) is kept which is used to trigger the 2935 sending of a Join(*,G) to the upstream next hop towards the RP, 2936 RPF'(*,G). 2938 Figure 7: Upstream (*,G) state machine in tabular form 2940 +--------------------++-------------------------------------------------+ 2941 | || Event | 2942 | Prev State ++------------------------+------------------------+ 2943 | || JoinDesired(*,G) | JoinDesired(*,G) | 2944 | || ->True | ->False | 2945 | 2946 +--------------------++------------------------+------------------------+ 2947 | || -> J state | - | 2948 | NotJoined (NJ) || Send Join(*,G); | | 2949 | || Set Join Timer to | | 2950 | || t_periodic | | 2951 | 2952 +--------------------++------------------------+------------------------+ 2953 | Joined (J) || - | -> NJ state | 2954 | || | Send Prune(*,G); | 2955 | || | Cancel Join Timer | 2956 | 2957 +--------------------++------------------------+------------------------+ 2959 In addition, we have the following transitions which occur within the 2960 Joined state: 2962 i+-----------------------------------------------------------------------+ 2963 | In Joined (J) State | 2964 | 2965 +-----------------+-----------------+-----------------+-----------------+ 2966 |Timer Expires | See Join(*,G) | See Prune(*,G) | RPF'(*,G) | 2967 | | to RPF'(*,G) | to RPF'(*,G) | changes due to | 2968 | | | | an Assert | 2969 | 2970 +-----------------+-----------------+-----------------+-----------------+ 2971 |Send | Increase Join | Decrease Join | Decrease Join | 2972 |Join(*,G); Set | Timer to | Timer to | Timer to | 2973 |Join Timer to | t_joinsuppress | t_override | t_override | 2974 |t_periodic | | | | 2975 | 2976 +-----------------+-----------------+-----------------+-----------------+ 2978 -+-----------------------------------------------------------------------+ 2979 | In Joined (J) State | 2980 | 2981 +----------------------------------+------------------------------------+ 2982 | RPF'(*,G) changes not | RPF'(*,G) GenID changes | 2983 | due to an Assert | | 2984 | 2985 +----------------------------------+------------------------------------+ 2986 | Send Join(*,G) to new | Decrease Join Timer to | 2987 | next hop; Send | t_override | 2988 | Prune(*,G) to old next | | 2989 | hop; Set Join Timer to | | 2990 | t_periodic | | 2991 | 2992 +----------------------------------+------------------------------------+ 2993 This state machine uses the following macro: 2995 bool JoinDesired(*,G) { 2996 if (immediate_olist(*,G) != NULL OR 2997 (JoinDesired(*,*,RP(G)) AND 2998 AssertWinner(*, G, RPF_interface(RP(G))) != NULL)) 2999 return TRUE 3000 else 3001 return FALSE 3002 } 3004 JoinDesired(*,G) is true when the router has forwarding state that would 3005 cause it to forward traffic for G using shared tree state. Note that 3006 although JoinDesired is true, the router's sending of a Join(*,G) 3007 message may be suppressed by another router sending a Join(*,G) onto the 3008 upstream interface. 3010 Transitions from NotJoined State 3012 When the upstream (*,G) state machine is in NotJoined state, the 3013 following event may trigger a state transition: 3015 JoinDesired(*,G) becomes True 3016 The macro JoinDesired(*,G) becomes True, e.g., because the 3017 downstream state for (*,G) has changed so that at least one 3018 interface is in immediate_olist(*,G). 3020 The upstream (*,G) state machine transitions to Joined state. 3021 Send Join(*,G) to the appropriate upstream neighbor, which is 3022 RPF'(*,G). Set the Join Timer (JT) to expire after t_periodic 3023 seconds. 3025 Transitions from Joined State 3027 When the upstream (*,G) state machine is in Joined state, the following 3028 events may trigger state transitions: 3030 JoinDesired(*,G) becomes False 3031 The macro JoinDesired(*,G) becomes False, e.g., because the 3032 downstream state for (*,G) has changed so no interface is in 3033 immediate_olist(*,G). 3035 The upstream (*,G) state machine transitions to NotJoined 3036 state. Send Prune(*,G) to the appropriate upstream neighbor, 3037 which is RPF'(*,G). Cancel the Join Timer (JT). 3039 Join Timer Expires 3040 The Join Timer (JT) expires, indicating time to send a 3041 Join(*,G) 3043 Send Join(*,G) to the appropriate upstream neighbor, which is 3044 RPF'(*,G). Restart the Join Timer (JT) to expire after 3045 t_periodic seconds. 3047 See Join(*,G) to RPF'(*,G) 3048 This event is only relevant if RPF_interface(RP(G)) is a 3049 shared medium. This router sees another router on 3050 RPF_interface(RP(G)) send a Join(*,G) to RPF'(*,G). This 3051 causes this router to suppress its own Join. 3053 The upstream (*,G) state machine remains in Joined state. 3055 Let t_joinsuppress be the minimum of t_suppressed and the 3056 HoldTime from the Join/Prune message triggering this event. 3057 If the Join Timer is set to expire in less than t_joinsuppress 3058 seconds, reset it so that it expires after t_joinsuppress 3059 seconds. If the Join Timer is set to expire in more than 3060 t_joinsuppress seconds, leave it unchanged. 3062 See Prune(*,G) to RPF'(*,G) 3063 This event is only relevant if RPF_interface(RP(G)) is a 3064 shared medium. This router sees another router on 3065 RPF_interface(RP(G)) send a Prune(*,G) to RPF'(*,G). As this 3066 router is in Joined state, it must override the Prune after a 3067 short random interval. 3069 The upstream (*,G) state machine remains in Joined state. If 3070 the Join Timer is set to expire in more than t_override 3071 seconds, reset it so that it expires after t_override seconds. 3072 If the Join Timer is set to expire in less than t_override 3073 seconds, leave it unchanged. 3075 RPF'(*,G) changes due to an Assert 3076 The current next hop towards the RP changes due to an 3077 Assert(*,G) on the RPF_interface(RP(G)). 3079 The upstream (*,G) state machine remains in Joined state. If 3080 the Join Timer is set to expire in more than t_override 3081 seconds, reset it so that it expires after t_override seconds. 3082 If the Join Timer is set to expire in less than t_override 3083 seconds, leave it unchanged. 3085 RPF'(*,G) changes not due to an Assert 3086 An event occurred which caused the next hop towards the RP for 3087 G to change. This may be caused by a change in the MRIB 3088 routing database or the group-to-RP mapping. Note that this 3089 transition does not occur if an Assert is active and the 3090 upstream interface does not change. 3092 The upstream (*,G) state machine remains in Joined state. 3093 Send Join(*,G) to the new upstream neighbor which is the new 3094 value of RPF'(*,G). Send Prune(*,G) to the old upstream 3095 neighbor, which is the old value of RPF'(*,G). Set the Join 3096 Timer (JT) to expire after t_periodic seconds. 3098 RPF'(*,G) GenID changes 3099 The Generation ID of the router that is RPF'(*,G) changes. 3100 This normally means that this neighbor has lost state, and so 3101 the state must be refreshed. 3103 The upstream (*,G) state machine remains in Joined state. If 3104 the Join Timer is set to expire in more than t_override 3105 seconds, reset it so that it expires after t_override seconds. 3107 4.5.7. Sending (S,G) Join/Prune Messages 3109 The per-interface state machines for (S,G) hold join state from 3110 downstream PIM routers. This state then determines whether a router 3111 needs to propagate a Join(S,G) upstream towards the source. 3113 If a router wishes to propagate a Join(S,G) upstream, it must also watch 3114 for messages on its upstream interface from other routers on that 3115 subnet, and these may modify its behavior. If it sees a Join(S,G) to 3116 the correct upstream neighbor, it should suppress its own Join(S,G). If 3117 it sees a Prune(S,G), Prune(S,G,rpt), or Prune(*,G) to the correct 3118 upstream neighbor towards S, it should be prepared to override that 3119 prune by scheduling a Join(S,G) to be sent almost immediately. Finally, 3120 if it sees the Generation ID of its upstream neighbor change, it knows 3121 that the upstream neighbor has lost state, and it should refresh the 3122 state by scheduling a Join(S,G) to be sent almost immediately. 3124 If a (S,G) Assert occurs on the upstream interface, and this changes the 3125 this router's idea of the upstream neighbor, it should be prepared to 3126 ensure that the Assert winner is aware of downstream routers by 3127 scheduling a Join(S,G) to be sent almost immediately. 3129 In addition, if MRIB changes cause the next hop towards the source to 3130 change, and either the upstream interface changes or there is no Assert 3131 winner on the upstream interface, the router should send a prune to the 3132 old next hop, and a join to the new next hop. 3134 The upstream (S,G) state machine only contains two states: 3136 Not Joined 3137 The downstream state machines and local membership information do 3138 not indicate that the router needs to join the shortest-path tree 3139 for this (S,G). 3141 Joined 3142 The downstream state machines and local membership information 3143 indicate that the router should join the shortest-path tree for 3144 this (S,G). 3146 In addition, one timer JT(S,G) is kept which is used to trigger the 3147 sending of a Join(S,G) to the upstream next hop towards S, RPF'(S,G). 3149 Figure 8: Upstream (S,G) state machine in tabular form 3151 +--------------------+--------------------------------------------------+ 3152 | | Event | 3153 | Prev State +-------------------------+------------------------+ 3154 | | JoinDesired(S,G) | JoinDesired(S,G) | 3155 | | ->True | ->False | 3156 | 3157 +--------------------+-------------------------+------------------------+ 3158 | NotJoined (NJ) | -> J state | - | 3159 | | Send Join(S,G); | | 3160 | | Set Join Timer to | | 3161 | | t_periodic | | 3162 | 3163 +--------------------+-------------------------+------------------------+ 3164 | Joined (J) | - | -> NJ state | 3165 | | | Send Prune(S,G); | 3166 | | | Set SPTbit(S,G) to | 3167 | | | FALSE; Cancel Join | 3168 | | | Timer | 3169 | 3170 +--------------------+-------------------------+------------------------+ 3171 In addition, we have the following transitions which occur within the 3172 Joined state: 3174 i+-----------------------------------------------------------------------+ 3175 | In Joined (J) State | 3176 | 3177 +-----------------+-----------------+------------------+----------------+ 3178 | Timer Expires | See Join(S,G) | See Prune(S,G) | See Prune | 3179 | | to RPF'(S,G) | to RPF'(S,G) | (S,G,rpt) to | 3180 | | | | RPF'(S,G) | 3181 | 3182 +-----------------+-----------------+------------------+----------------+ 3183 | Send | Increase Join | Decrease Join | Decrease Join | 3184 | Join(S,G); Set | Timer to | Timer to | Timer to | 3185 | Join Timer to | t_joinsuppress | t_override | t_override | 3186 | t_periodic | | | | 3187 | 3188 +-----------------+-----------------+------------------+----------------+ 3190 -+-----------------------------------------------------------------------+ 3191 | In Joined (J) State | 3192 | 3193 +-----------------+-----------------+-----------------+-----------------+ 3194 | See Prune(*,G) | RPF'(S,G) | RPF'(S,G) | RPF'(S,G) | 3195 | to RPF'(S,G) | changes not | GenID changes | changes due to | 3196 | | due to an | | an Assert | 3197 | | Assert | | | 3198 | 3199 +-----------------+-----------------+-----------------+-----------------+ 3200 | Decrease Join | Send Join(S,G) | Decrease Join | Decrease Join | 3201 | Timer to | to new next | Timer to | Timer to | 3202 | t_override | hop; Send | t_override | t_override | 3203 | | Prune(S,G) to | | | 3204 | | old next hop; | | | 3205 | | Set Join Timer | | | 3206 | | to t_periodic | | | 3207 | 3208 +-----------------+-----------------+-----------------+-----------------+ 3210 This state machine uses the following macro: 3212 bool JoinDesired(S,G) { 3213 return( immediate_olist(S,G) != NULL 3214 OR ( KeepaliveTimer(S,G) is running 3215 AND inherited_olist(S,G) != NULL ) ) 3216 } 3218 JoinDesired(S,G) is true when the router has forwarding state that would 3219 cause it to forward traffic for G using source tree state. The source 3220 tree state can either be as a result of active source-specific join 3221 state, or the (S,G) Keepalive Timer and active non-source-specific 3222 state. Note that although JoinDesired is true, the router's sending of a 3223 Join(S,G) message may be suppressed by another router sending a 3224 Join(S,G) onto the upstream interface. 3226 Transitions from NotJoined State 3228 When the upstream (S,G) state machine is in NotJoined state, the 3229 following event may trigger a state transition: 3231 JoinDesired(S,G) becomes True 3232 The macro JoinDesired(S,G) becomes True, e.g., because the 3233 downstream state for (S,G) has changed so that at least one 3234 interface is in inherited_olist(S,G). 3236 The upstream (S,G) state machine transitions to Joined state. 3237 Send Join(S,G) to the appropriate upstream neighbor, which is 3238 RPF'(S,G). Set the Join Timer (JT) to expire after t_periodic 3239 seconds. 3241 Transitions from Joined State 3243 When the upstream (S,G) state machine is in Joined state, the following 3244 events may trigger state transitions: 3246 JoinDesired(S,G) becomes False 3247 The macro JoinDesired(S,G) becomes False, e.g., because the 3248 downstream state for (S,G) has changed so no interface is in 3249 inherited_olist(S,G). 3251 The upstream (S,G) state machine transitions to NotJoined 3252 state. Send Prune(S,G) to the appropriate upstream neighbor, 3253 which is RPF'(S,G). Cancel the Join Timer (JT), and set 3254 SPTbit(S,G) to FALSE. 3256 Join Timer Expires 3257 The Join Timer (JT) expires, indicating time to send a 3258 Join(S,G) 3260 Send Join(S,G) to the appropriate upstream neighbor, which is 3261 RPF'(S,G). Restart the Join Timer (JT) to expire after 3262 t_periodic seconds. 3264 See Join(S,G) to RPF'(S,G) 3265 This event is only relevant if RPF_interface(S) is a shared 3266 medium. This router sees another router on RPF_interface(S) 3267 send a Join(S,G) to RPF'(S,G). This causes this router to 3268 suppress its own Join. 3270 The upstream (S,G) state machine remains in Joined state. 3272 Let t_joinsuppress be the minimum of t_suppressed and the 3273 HoldTime from the Join/Prune message triggering this event. 3275 If the Join Timer is set to expire in less than t_joinsuppress 3276 seconds, reset it so that it expires after t_joinsuppress 3277 seconds. If the Join Timer is set to expire in more than 3278 t_joinsuppress seconds, leave it unchanged. 3280 See Prune(S,G) to RPF'(S,G) 3281 This event is only relevant if RPF_interface(S) is a shared 3282 medium. This router sees another router on RPF_interface(S) 3283 send a Prune(S,G) to RPF'(S,G). As this router is in Joined 3284 state, it must override the Prune after a short random 3285 interval. 3287 The upstream (S,G) state machine remains in Joined state. If 3288 the Join Timer is set to expire in more than t_override 3289 seconds, reset it so that it expires after t_override seconds. 3291 See Prune(S,G,rpt) to RPF'(S,G) 3292 This event is only relevant if RPF_interface(S) is a shared 3293 medium. This router sees another router on RPF_interface(S) 3294 send a Prune(S,G,rpt) to RPF'(S,G). If the upstream router is 3295 an RFC 2362 compliant PIM router, then the Prune(S,G,rpt) will 3296 cause it to stop forwarding. For backwards compatibility, 3297 this router should override the prune so that forwarding 3298 continues. 3300 The upstream (S,G) state machine remains in Joined state. If 3301 the Join Timer is set to expire in more than t_override 3302 seconds, reset it so that it expires after t_override seconds. 3304 See Prune(*,G) to RPF'(S,G) 3305 This event is only relevant if RPF_interface(S) is a shared 3306 medium. This router sees another router on RPF_interface(S) 3307 send a Prune(*,G) to RPF'(S,G). If the upstream router is an 3308 RFC 2362 compliant PIM router, then the Prune(*,G) will cause 3309 it to stop forwarding. For backwards compatibility, this 3310 router should override the prune so that forwarding continues. 3312 The upstream (S,G) state machine remains in Joined state. If 3313 the Join Timer is set to expire in more than t_override 3314 seconds, reset it so that it expires after t_override seconds. 3316 RPF'(S,G) changes due to an Assert 3317 The current next hop towards S changes due to an Assert(S,G) 3318 on the RPF_interface(S). 3320 The upstream (S,G) state machine remains in Joined state. If 3321 the Join Timer is set to expire in more than t_override 3322 seconds, reset it so that it expires after t_override seconds. 3324 If the Join Timer is set to expire in less than t_override 3325 seconds, leave it unchanged. 3327 RPF'(S,G) changes not due to an Assert 3328 An event occurred which caused the next hop towards S to 3329 change. Note that this transition does not occur if an Assert 3330 is active and the upstream interface does not change. 3332 The upstream (S,G) state machine remains in Joined state. 3333 Send Join(S,G) to the new upstream neighbor which is the new 3334 value of RPF'(S,G). Send Prune(S,G) to the old upstream 3335 neighbor, which is the old value of RPF'(S,G). Set the Join 3336 Timer (JT) to expire after t_periodic seconds. 3338 RPF'(S,G) GenID changes 3339 The Generation ID of the router that is RPF'(S,G) changes. 3340 This normally means that this neighbor has lost state, and so 3341 the state must be refreshed. 3343 The upstream (S,G) state machine remains in Joined state. If 3344 the Join Timer is set to expire in more than t_override 3345 seconds, reset it so that it expires after t_override seconds. 3347 4.5.8. (S,G,rpt) Periodic Messages 3349 (S,G,rpt) Joins and Prunes are (S,G) Joins or Prunes sent on the RP tree 3350 with the RPT bit set, either to modify the results of (*,G) Joins, or to 3351 override the behavior of other upstream LAN peers. The next section 3352 describes the rules for sending triggered messages. This section 3353 describes the rules for including a Prune(S,G,rpt) message with a 3354 Join(*,G). 3356 When a router is going to send a Join(*,G), it should use the following 3357 pseudocode, for each (S,G) for which it has state, to decide whether to 3358 include a Prune(S,G,rpt) in the compound Join/Prune message: 3360 if( SPTbit(S,G) == TRUE ) { 3361 # Note: If receiving (S,G) on the SPT, we only prune off the 3362 # shared tree if the RPF neighbors differ. 3363 if( RPF'(*,G) != RPF'(S,G) ) { 3364 add Prune(S,G,rpt) to compound message 3365 } 3366 } else if ( inherited_olist(S,G,rpt) == NULL ) { 3367 # Note: all (*,G) olist interfaces received RPT prunes for (S,G). 3368 add Prune(S,G,rpt) to compound message 3369 } else if ( RPF'(*,G) != RPF'(S,G,rpt) { 3370 # Note: we joined the shared tree, but there was an (S,G) assert and 3371 # the source tree RPF neighbor is different. 3372 add Prune(S,G,rpt) to compound message 3373 } 3375 Note that Join(S,G,rpt) is not normally sent as a periodic message, but 3376 only as a triggered message. 3378 4.5.9. State Machine for (S,G,rpt) Triggered Messages 3380 The state machine for (S,G,rpt) triggered messages is required per-(S,G) 3381 when there is (*,G) or (*,*,RP) join state at a router, and the router 3382 or any of its upstream LAN peers wishes to prune S off the RP tree. 3384 There are three states in the state machine. One of the states is when 3385 there is neither (*,G) nor (*,*,RP(G)) join state at this router. If 3386 there is (*,G) or (*,*,RP(G)) join state at the router, then the state 3387 machine must be at one of the other two states. The three states are: 3389 Pruned(S,G,rpt) 3390 (*,G) or (*,*,RP(G)) Joined, but (S,G,rpt) pruned 3392 NotPruned(S,G,rpt) 3393 (*,G) or (*,*,RP(G)) Joined, and (S,G,rpt) not pruned 3395 RPTNotJoined(G) 3396 neither (*,G) nor (*,*,RP(G)) has been joined. 3398 In addition, there is an (S,G,rpt) Override Timer, OT(S,G,rpt), which is 3399 used to delay triggered Join(S,G,rpt) messages to prevent implosions of 3400 triggered messages. 3402 Figure 9: Upstream (S,G,rpt) state machine for triggered messages in 3403 tabular form 3405 +---------------++-------------------------------------------------------------+ 3406 | || Event | 3407 | ++---------------+---------------+--------------+--------------+ 3408 |Prev State || PruneDesired | PruneDesired | RPTJoin | inherited_ | 3409 | || (S,G,rpt) | (S,G,rpt) | Desired(G) | olist | 3410 | || ->True | ->False | ->False | (S,G,rpt) | 3411 | || | | | ->non-NULL | 3412 ->n+---------------++---------------+---------------+--------------+--------------+ 3413 |RPTNotJoined || -> P state | - | - | -> NP state | 3414 |(G) (NJ) || | | | | 3415 +---------------++---------------+---------------+--------------+--------------+ 3416 |Pruned || - | -> NP state | -> NJ state | - | 3417 |(S,G,rpt) (P) || | Send Join | | | 3418 | || | (S,G,rpt) | | | 3419 +---------------++---------------+---------------+--------------+--------------+ 3420 |NotPruned || -> P state | - | -> NJ state | - | 3421 |(S,G,rpt) || Send Prune | | Cancel OT | | 3422 |(NP) || (S,G,rpt); | | | | 3423 | || Cancel OT | | | | 3424 +---------------++---------------+---------------+--------------+--------------+ 3425 Additionally, we have the following transitions within the 3426 NotPruned(S,G,rpt) state which are all used for prune override behavior. 3428 t+-----------------------------------------------------------------------+ 3429 | In NotPruned(S,G,rpt) State | 3430 | 3431 +-----------+--------------+--------------+--------------+--------------+ 3432 |Override | See Prune | See Join | See Prune | RPF' | 3433 |Timer | (S,G,rpt) to | (S,G,rpt) to | (S,G) to | (S,G,rpt) -> | 3434 |expires | RPF' | RPF' | RPF' | RPF' (*,G) | 3435 | | (S,G,rpt) | (S,G,rpt) | (S,G,rpt) | | 3436 | 3437 +-----------+--------------+--------------+--------------+--------------+ 3438 |Send Join | OT = min(OT, | Cancel OT | OT = min(OT, | OT = min(OT, | 3439 |(S,G,rpt); | t_override) | | t_override) | t_override) | 3440 |Leave OT | | | | | 3441 |unset | | | | | 3442 | 3443 +-----------+--------------+--------------+--------------+--------------+ 3445 Note that the min function in the above state machine considers a non- 3446 running timer to have an infinite value (e.g. min(not-running, 3447 t_override) = t_override). 3449 This state machine uses the following macros: 3451 bool RPTJoinDesired(G) { 3452 return (JoinDesired(*,G) OR JoinDesired(*,*,RP(G))) 3453 } 3455 RPTJoinDesired(G) is true when the router has forwarding state that 3456 would cause it to forward traffic for G using either (*,G) or (*,*,RP) 3457 shared tree state. 3459 bool PruneDesired(S,G,rpt) { 3460 return ( RPTJoinDesired(G) AND 3461 ( inherited_olist(S,G,rpt) == NULL 3462 OR (SPTbit(S,G)==TRUE 3463 AND (RPF'(*,G) != RPF'(S,G)) ))) 3464 } 3466 PruneDesired(S,G,rpt) can only be true if RPTJoinDesired(G) is true. If 3467 RPTJoinDesired(G) is true, then PruneDesired(S,G,rpt) is true if either 3468 there are no outgoing interfaces that S would be forwarded on, or if the 3469 router has active (S,G) forwarding state but RPF'(*,G) != RPF'(S,G). 3471 The state machine contains the following transition events: 3473 See Join(S,G,rpt) to RPF'(S,G,rpt) 3474 This event is only relevant in the "Not Pruned" state. 3476 The router sees a Join(S,G,rpt) from someone else to RPF'(S,G,rpt), 3477 which is the correct upstream neighbor. If we're in "NotPruned" 3478 state and the (S,G,rpt) Override Timer is running, then this is 3479 because we have been triggered to send our own Join(S,G,rpt) to 3480 RPF'(S,G,rpt). Someone else beat us to it, so there's no need to 3481 send our own Join. 3483 The action is to cancel the Override Timer. 3485 See Prune(S,G,rpt) to RPF'(S,G,rpt) 3486 This event is only relevant in the "NotPruned" state. 3488 The router sees a Prune(S,G,rpt) from someone else to to 3489 RPF'(S,G,rpt), which is the correct upstream neighbor. If we're in 3490 the "NotPruned" state, then we want to continue to receive traffic 3491 from S destined for G, and that traffic is being supplied by 3492 RPF'(S,G,rpt). Thus we need to override the Prune. 3494 The action is to set the (S,G,rpt) Override Timer to the randomized 3495 prune-override interval, t_override. However if the Override Timer 3496 is already running, we only set the timer if doing so would set it 3497 to a lower value. At the end of this interval, if no-one else has 3498 sent a Join, then we will do so. 3500 See Prune(S,G) to RPF'(S,G,rpt) 3501 This event is only relevant in the "NotPruned" state. 3503 This transition and action are the same as the above transition and 3504 action, except that the Prune does not have the RPT bit set. This 3505 transition is necessary to be compatible with routers implemented 3506 from RFC2362 that don't maintain separate (S,G) and (S,G,rpt) 3507 state. 3509 The (S,G,rpt) prune Override Timer expires 3510 This event is only relevant in the "NotPruned" state. 3512 When the Override Timer expires, we must send a Join(S,G,rpt) to 3513 RPF'(S,G,rpt) to override the Prune message that caused the timer 3514 to be running. We only send this if RPF'(S,G,rpt) equals RPF'(*,G) 3515 - if this were not the case, then the Join might be sent to a 3516 router that does not have (*,G) or (*,*,RP(G)) Join state, and so 3517 the behavior would not be well defined. If RPF'(S,G,rpt) is not 3518 the same as RPF'(*,G), then it may stop forwarding S. However, if 3519 this happens, then the router will send an AssertCancel(S,G), which 3520 would then cause RPF'(S,G,rpt) to become equal to RPF'(*,G) (see 3521 below). 3523 RPF'(S,G,rpt) changes to become equal to RPF'(*,G) 3524 This event is only relevant in the "NotPruned" state. 3526 RPF'(S,G,rpt) can only be different from RPF'(*,G) if an (S,G) 3527 Assert has happened, which means that traffic from S is arriving on 3528 the SPT, and so Prune(S,G,rpt) will have been sent to RPF'(*,G). 3529 When RPF'(S,G,rpt) changes to become equal to RPF'(*,G), we need to 3530 trigger a Join(S,G,rpt) to RPF'(*,G) to cause that router to start 3531 forwarding S again. 3533 The action is to set the (S,G,rpt) Override Timer to the randomized 3534 prune-override interval t_override. However if the timer is 3535 already running, we only set the timer if doing so would set it to 3536 a lower value. At the end of this interval, if no-one else has 3537 sent a Join, then we will do so. 3539 PruneDesired(S,G,rpt)->TRUE 3540 See macro above. This event is relevant in the "NotPruned" and 3541 "RPTNotJoined(G)" states. 3543 The router wishes to receive traffic for G, but does not wish to 3544 receive traffic from S destined for G. This causes the router to 3545 transition into the Pruned state. 3547 If the router was previously in NotPruned state, then the action is 3548 to send a Prune(S,G,rpt) to RPF'(S,G,rpt), and to cancel the 3549 Override Timer. If the router was previously in RPTNotJoined(G) 3550 state, then there is no need to trigger an action in this state 3551 machine because sending a Prune(S,G,rpt) is handled by the rules 3552 for sending the Join(*,G) or Join(*,*,RP). 3554 PruneDesired(S,G,rpt)->FALSE 3555 See macro above. This transition is only relevant in the "Pruned" 3556 state. 3558 If the router is in the Pruned(S,G,rpt) state, and 3559 PruneDesired(S,G,rpt) changes to FALSE, this could be because the 3560 router no longer has RPTJoinDesired(G) true, or it now wishes to 3561 receive traffic from S again. If it is the former, then this 3562 transition should not happen, but instead the 3563 "RPTJoinDesired(G)->FALSE" transition should happen. Thus this 3564 transition should be interpreted as "PruneDesired(S,G,rpt)->FALSE 3565 AND RPTJoinDesired(G)==TRUE" 3567 The action is to send a Join(S,G,rpt) to RPF'(S,G,rpt). 3569 RPTJoinDesired(G)->FALSE 3570 This event is relevant in the "Pruned" and "NotPruned" states. 3572 The router no longer wishes to receive any traffic destined for G 3573 on the RP Tree. This causes a transition to the RPTNotJoined(G) 3574 state, and the Override Timer is canceled if it was running. Any 3575 further actions are handled by the appropriate upstream state 3576 machine for (*,G) or (*,*,RP). 3578 inherited_olist(S,G,rpt) becomes non-NULL 3579 This transition is only relevant in the RPTNotJoined(G) state. 3581 The router has joined the RP tree (handled by the (*,G) or (*,*,RP) 3582 upstream state machine as appropriate), and wants to receive 3583 traffic from S. This does not trigger any events in this state 3584 machine, but causes a transition to the NotPruned(S,G,rpt) state. 3586 4.5.10. Background: (*,*,RP) and (S,G,rpt) Interaction 3588 In sections 4.5.8 and 4.5.9 the mechanisms for sending periodic and 3589 triggered (S,G,rpt) messages are described. The astute reader will note 3590 that periodic Prune(S,G,rpt) messages are only sent in PIM Join/Prune 3591 messages containing a Join(*,G), whereas it is possible for a triggered 3592 Prune(S,G,rpt) message to be sent when the router has no (*,G) join 3593 state. This may seem like a contradiction, but in fact it is 3594 intentional, and is a side effect of not optimizing (*,*,RP) behavior. 3596 We first note that reception of a Join(*,*,RP) by itself does not cancel 3597 (S,G,rpt) prune state on that interface, whereas receiving a Join(*,G) 3598 by itself does cancel (S,G,rpt) prune state on that interface. 3599 Similarly, reception of a Prune(*,G) on an interface with (*,*,RP) join 3600 state does not by itself prevent forwarding of G using the (*,*,RP) 3601 state - this is because a Prune(*,G) only serves to cancel (*,G) join 3602 state. Conceptually (*,*,RP) state functions "above" the normal (*,G) 3603 and (S,G) mechanisms, and so neither Join(*,*,RP) or Prune(*,*,RP) 3604 messages affect any other state. 3606 The upshot of this is that to prevent forwarding (S,G) on (*,*,RP) 3607 state, a Prune(S,G,rpt) must be used. 3609 We also note that for historical reasons there is no Assert(*,*,RP) 3610 message, so any forwarding contention is resolved using Assert(*,G) 3611 messages. 3613 We now need to consider the interaction between (*,*,RP) state and (*,G) 3614 state. If there is a need for an assert between two upstream routers on 3615 a LAN, we need to ensure that the correct thing happens for all 3616 combinations of (*,*,RP) and (*,G) forwarding state. As there is no 3617 Assert(*,*,RP) message, no router can tell whether the assert winner has 3618 (*,*,RP) state or (*,G) state. Thus a downstream router has to treat 3619 the two the same and send its periodic Prune(S,G,rpt) messages to 3620 RPF'(*,G). 3622 To avoid needing to specify all the complex override rules between 3623 (*,*,RP), (*,G) and (S,G,rpt), we simply require that to prune (S,G) off 3624 the (*,*,RP) tree, a Join(*,G) must also be sent. 3626 If a router is receiving on (*,*,RP) state, and has not yet had (*,G) 3627 state instantiated, it may still need to send a triggered Join(S,G,rpt) 3628 to override a Prune(S,G,rpt) that it sees directed to RPF'(*,G) on its 3629 upstream interface. Hence triggered (S,G,rpt) messages may be sent when 3630 JoinDesired(*,G) is false but JoinDesired(*,*,RP) is true. 3632 Finally we note that there is an unoptimized case when the upstream 3633 router on a LAN already has (*,G) join and (S,G,rpt) prune state caused 3634 by an existing downstream router. If at this time a new Join(*,*,RP) is 3635 sent to the upstream router from a different downstream router, this 3636 will not override the (S,G,rpt) prune state at the upstream router. The 3637 override will not occur until the next time the original downstream 3638 router resends its Prune(S,G,rpt). This case was considered to be not 3639 worth optimizing, as (*,*,RP) state is generally very long lived, and so 3640 any minor delays in getting traffic to a new PMBR seem unimportant. 3642 4.6. PIM Assert Messages 3644 Where multiple PIM routers peer over a shared LAN it is possible for 3645 more than one upstream router to have valid forwarding state for a 3646 packet, which can lead to packet duplication (see Section 3 "Multi- 3647 access LANs"). PIM does not attempt to prevent this from occurring. 3648 Instead it detects when this has happened and elects a single forwarder 3649 amongst the upstream routers to prevent further duplication. This 3650 election is performed using PIM Assert messages. Assert messages are 3651 also received by downstream routers on the LAN, and these cause 3652 subsequent Join/Prune messages to be sent to the upstream router that 3653 won the Assert. 3655 In general, a PIM Assert message should only be accepted for processing 3656 if it comes from a known PIM neighbor. A PIM router hears about PIM 3657 neighbors through PIM Hello messages. If a router receives an Assert 3658 message from a particular IP source address and it has not seen a PIM 3659 Hello message from that source address, then the Assert message SHOULD 3660 be discarded without further processing. In addition, if the Hello 3661 message from a neighbor was authenticated using the IPsec Authentication 3662 Header (AH) (see Section 6.3) then all Assert messages from that 3663 neighbor MUST also be authenticated using IPsec AH. 3665 We note that some older PIM implementations incorrectly fail to send 3666 Hello messages on point-to-point interfaces, so we also RECOMMEND that a 3667 configuration option be provided to allow interoperation with such older 3668 routers, but that this configuration option SHOULD NOT be enabled by 3669 default. 3671 4.6.1. (S,G) Assert Message State Machine 3673 The (S,G) Assert state machine for interface I is shown in Figure 10. 3674 There are three states: 3676 NoInfo (NI) 3677 This router has no (S,G) assert state on interface I. 3679 I am Assert Winner (W) 3680 This router has won an (S,G) assert on interface I. It is now 3681 responsible for forwarding traffic from S destined for G out of 3682 interface I. Irrespective of whether it is the DR for I, while a 3683 router is the assert winner, it is also responsible for forwarding 3684 traffic onto I on behalf of local hosts on I that have made 3685 membership requests that specifically refer to S (and G). 3687 I am Assert Loser (L) 3688 This router has lost an (S,G) assert on interface I. It must not 3689 forward packets from S destined for G onto interface I. If it is 3690 the DR on I, it is no longer responsible for forwarding traffic 3691 onto I to satisfy local hosts with membership requests that 3692 specifically refer to S and G. 3694 In addition, there is also an Assert Timer (AT) that is used to time out 3695 asserts on the assert losers and to resend asserts on the assert winner. 3697 Figure 10: Per-interface (S,G) Assert State machine in tabular form 3699 F+-----------------------------------------------------------------------+ 3700 | In NoInfo (NI) State | 3701 | 3702 +---------------+-------------------+------------------+----------------+ 3703 | Receive | Receive Assert | Data arrives | Receive | 3704 | Inferior | with RPTbit | from S to G on | Acceptable | 3705 | Assert with | set and | I and | Assert with | 3706 | RPTbit clear | CouldAssert | CouldAssert | RPTbit clear | 3707 | and | (S,G,I) | (S,G,I) | and AssTrDes | 3708 | CouldAssert | | | (S,G,I) | 3709 | (S,G,I) | | | | 3710 | 3711 +---------------+-------------------+------------------+----------------+ 3712 | -> W state | -> W state | -> W state | -> L state | 3713 | [Actions A1] | [Actions A1] | [Actions A1] | [Actions A6] | 3714 | 3715 +---------------+-------------------+------------------+----------------+ 3717 -+-----------------------------------------------------------------------+ 3718 | In I Am Assert Winner (W) State | 3719 | 3720 +----------------+------------------+-----------------+-----------------+ 3721 | Assert Timer | Receive | Receive | CouldAssert | 3722 | Expires | Inferior | Preferred | (S,G,I) -> | 3723 | | Assert | Assert | FALSE | 3724 | 3725 +----------------+------------------+-----------------+-----------------+ 3726 | -> W state | -> W state | -> L state | -> NI state | 3727 | [Actions A3] | [Actions A3] | [Actions A2] | [Actions A4] | 3728 | 3729 +----------------+------------------+-----------------+-----------------+ 3731 -+---------------------------------------------------------------------------+ 3732 | In I Am Assert Loser (L) State | 3733 +-------------+----------------+--------------+--------------+--------------+ 3734 |Receive | Receive | | Receive | Assert Timer | Current | 3735 |Preferred | Acceptable | | Inferior | Expires | Winner's | 3736 |Assert | Assert with | | Assert from | | GenID | 3737 | | RPTbit clear | | Current | | Changes or | 3738 | | from Current | | Winner | | NLT Expires | 3739 | | Winner | | | | 3740 +-------------+----------------+--------------+--------------+--------------+ 3741 |-> L state | -> L state | -> NI state | -> NI state | -> NI state | 3742 |[Actions A2] | [Actions A2] | [Actions A5] | [Actions A5] | [Actions A5] | 3743 A5]+-------------+----------------+--------------+--------------+--------------+ 3744 T+-----------------------------------------------------------------------+ 3745 | In I Am Assert Loser (L) State | 3746 | 3747 +----------------+-----------------+-------------------+----------------+ 3748 | AssTrDes | my_metric -> | RPF_interface | Receive | 3749 | (S,G,I) -> | better than | (S) stops | Join(S,G) on | 3750 | FALSE | winner's | being I | interface I | 3751 | | metric | | | 3752 | 3753 +----------------+-----------------+-------------------+----------------+ 3754 | -> NI state | -> NI state | -> NI state | -> NI State | 3755 | [Actions A5] | [Actions A5] | [Actions A5] | [Actions A5] | 3756 | 3757 +----------------+-----------------+-------------------+----------------+ 3759 Note that for reasons of compactness, "AssTrDes(S,G,I)" is used in the 3760 state machine table to refer to AssertTrackingDesired(S,G,I). 3762 Terminology: 3763 A "preferred assert" is one with a better metric than the current 3764 winner. 3766 An "acceptable assert" is one that has a better metric than 3767 my_assert_metric(S,G,I). 3769 An "inferior assert" is one with a worse metric than 3770 my_assert_metric(S,G,I). 3771 The state machine uses the following macros: 3773 CouldAssert(S,G,I) = 3774 SPTbit(S,G)==TRUE 3775 AND (RPF_interface(S) != I) 3776 AND (I in ( ( joins(*,*,RP(G)) (+) joins(*,G) (-) prunes(S,G,rpt) ) 3777 (+) ( pim_include(*,G) (-) pim_exclude(S,G) ) 3778 (-) lost_assert(*,G) 3779 (+) joins(S,G) (+) pim_include(S,G) ) ) 3781 CouldAssert(S,G,I) is true for downstream interfaces which would be in 3782 the inherited_olist(S,G) if (S,G) assert information was not taken into 3783 account. 3785 AssertTrackingDesired(S,G,I) = 3786 (I in ( ( joins(*,*,RP(G)) (+) joins(*,G) (-) prunes(S,G,rpt) ) 3787 (+) ( pim_include(*,G) (-) pim_exclude(S,G) ) 3788 (-) lost_assert(*,G) 3789 (+) joins(S,G) ) ) 3790 OR (local_receiver_include(S,G,I) == TRUE 3791 AND (I_am_DR(I) OR (AssertWinner(S,G,I) == me))) 3792 OR ((RPF_interface(S) == I) AND (JoinDesired(S,G) == TRUE)) 3793 OR ((RPF_interface(RP(G)) == I) AND (JoinDesired(*,G) == TRUE) 3794 AND (SPTbit(S,G) == FALSE)) 3796 AssertTrackingDesired(S,G,I) is true on any interface in which an (S,G) 3797 assert might affect our behavior. 3799 The first three lines of AssertTrackingDesired account for (*,G) join 3800 and local membership information received on I that might cause the 3801 router to be interested in asserts on I. 3803 The 4th line accounts for (S,G) join information received on I that 3804 might cause the router to be interested in asserts on I. 3806 The 5th and 6th lines account for (S,G) local membership information on 3807 I. Note that we can't use the pim_include(S,G) macro since it uses 3808 lost_assert(S,G,I) and would result in the router forgetting that it 3809 lost an assert if the only reason it was interested was local 3810 membership. The AssertWinner(S,G,I) check forces an assert winner to 3811 keep on being responsible for forwarding as long as local receivers are 3812 present. Removing this check would make the assert winner give up 3813 forwarding as soon as the information that originally caused it to 3814 forward went away and the task of forwarding for local receivers would 3815 revert back to the DR. 3817 The last three lines account for the fact that a router must keep track 3818 of assert information on upstream interfaces in order to send joins and 3819 prunes to the proper neighbor. 3821 Transitions from NoInfo State 3823 When in NoInfo state, the following events may trigger transitions: 3825 Receive Inferior Assert with RPTbit cleared AND 3826 CouldAssert(S,G,I)==TRUE 3827 An assert is received for (S,G) with the RPT bit cleared that 3828 is inferior to our own assert metric. The RPT bit cleared 3829 indicates that the sender of the assert had (S,G) forwarding 3830 state on this interface. If the assert is inferior to our 3831 metric, then we must also have (S,G) forwarding state (i.e. 3832 CouldAssert(S,G,I)==TRUE) as (S,G) asserts beat (*,G) asserts, 3833 and so we should be the assert winner. We transition to the 3834 "I am Assert Winner" state, and perform Actions A1 (below). 3836 Receive Assert with RPTbit set AND CouldAssert(S,G,I)==TRUE 3837 An assert is received for (S,G) on I with the RPT bit set 3838 (it's a (*,G) assert). CouldAssert(S,G,I) is TRUE only if we 3839 have (S,G) forwarding state on this interface, so we should be 3840 the assert winner. We transition to the "I am Assert Winner" 3841 state, and perform Actions A1 (below). 3843 An (S,G) data packet arrives on interface I, AND 3844 CouldAssert(S,G,I)==TRUE 3845 An (S,G) data packet arrived on an downstream interface which 3846 is in our (S,G) outgoing interface list. We optimistically 3847 assume that we will be the assert winner for this (S,G), and 3848 so we transition to the "I am Assert Winner" state, and 3849 perform Actions A1 (below) which will initiate the assert 3850 negotiation for (S,G). 3852 Receive Acceptable Assert with RPT bit clear AND 3853 AssertTrackingDesired(S,G,I)==TRUE 3854 We're interested in (S,G) Asserts, either because I is a 3855 downstream interface for which we have (S,G) or (*,G) 3856 forwarding state, or because I is the upstream interface for S 3857 and we have (S,G) forwarding state. The received assert has a 3858 better metric than our own, so we do not win the Assert. We 3859 transition to "I am Assert Loser" and perform actions A6 3860 (below). 3862 Transitions from "I am Assert Winner" State 3864 When in "I am Assert Winner" state, the following events trigger 3865 transitions: 3867 Assert Timer Expires 3868 The (S,G) Assert Timer expires. As we're in the Winner state, 3869 then we must still have (S,G) forwarding state that is 3870 actively being kept alive. We re-send the (S,G) Assert and 3871 restart the Assert Timer (Action A3 below). Note that the 3872 assert winner's Assert Timer is engineered to expire shortly 3873 before timers on assert losers; this prevents unnecessary 3874 thrashing of the forwarder and periodic flooding of duplicate 3875 packets. 3877 Receive Inferior Assert 3878 We receive an (S,G) assert or (*,G) assert mentioning S that 3879 has a worse metric than our own. Whoever sent the assert is 3880 in error, and so we re-send an (S,G) Assert, and restart the 3881 Assert Timer (Action A3 below). 3883 Receive Preferred Assert 3884 We receive an (S,G) assert that has a better metric than our 3885 own. We transition to "I am Assert Loser" state and perform 3886 actions A2 (below). Note that this may affect the value of 3887 JoinDesired(S,G) and PruneDesired(S,G,rpt) which could cause 3888 transitions in the upstream (S,G) or (S,G,rpt) state machines. 3890 CouldAssert(S,G,I) -> FALSE 3891 Our (S,G) forwarding state or RPF interface changed so as to 3892 make CouldAssert(S,G,I) become false. We can no longer 3893 perform the actions of the assert winner, and so we transition 3894 to NoInfo state and perform actions A4 (below). This includes 3895 sending a "canceling assert" with an infinite metric. 3897 Transitions from "I am Assert Loser" State 3899 When in "I am Assert Loser" state, the following transitions can occur: 3901 Receive Preferred Assert 3902 We receive an assert that is better than that of the current 3903 assert winner. We stay in Loser state, and perform actions A2 3904 below. 3906 Receive Acceptable Assert with RPTbit clear from Current Winner 3907 We receive an assert from the current assert winner that is 3908 better than our own metric for this (S,G) (although the metric 3909 may be worse than the winner's previous metric). We stay in 3910 Loser state, and perform actions A2 below. 3912 Receive Inferior Assert from Current Winner 3913 We receive an assert from the current assert winner that is 3914 worse than our own metric for this group (typically the 3915 winner's metric became worse). We transition to NoInfo state, 3916 deleting the (S,G) assert information and allowing the normal 3917 PIM Join/Prune mechanisms to operate. Usually we will 3918 eventually re-assert and win when data packets from S have 3919 started flowing again. 3921 Assert Timer Expires 3922 The (S,G) Assert Timer expires. We transition to NoInfo 3923 state, deleting the (S,G) assert information (action A5 3924 below). 3926 Current Winner's GenID Changes or NLT Expires 3927 The Neighbor Liveness Timer associated with the current winner 3928 expires or we receive a Hello message from the current winner 3929 reporting a different GenID from the one it previously 3930 reported. This indicates that the current winner's interface 3931 or router has gone down (and may have come back up), and so we 3932 must assume it no longer knows it was the winner. We 3933 transition to the NoInfo state, deleting this (S,G) assert 3934 information (action A5 below). 3936 AssertTrackingDesired(S,G,I)->FALSE 3937 AssertTrackingDesired(S,G,I) becomes FALSE. Our forwarding 3938 state has changed so that (S,G) Asserts on interface I are no 3939 longer of interest to us. We transition to the NoInfo state, 3940 deleting the (S,G) assert information. 3942 My metric becomes better than the assert winner's metric 3943 my_assert_metric(S,G,I) has changed so that now my assert 3944 metric for (S,G) is better than the metric we have stored for 3945 current assert winner. This might happen the underlying 3946 routing metric changes, or when CouldAssert(S,G,I) becomes 3947 true; for example, when SPTbit(S,G) becomes true. We 3948 transition to NoInfo state, delete this (S,G) assert state 3949 (action A5 below), and allow the normal PIM Join/Prune 3950 mechanisms to operate. Usually we will eventually re-assert 3951 and win when data packets from S have started flowing again. 3953 RPF_interface(S) stops being interface I 3954 Interface I used to be the RPF interface for S, and now it is 3955 not. We transition to NoInfo state, deleting this (S,G) 3956 assert state (action A5 below). 3958 Receive Join(S,G) on Interface I 3959 We receive a Join(S,G) that has the Upstream Neighbor Address 3960 field set to my primary IP address on interface I. The action | 3961 is to transition to NoInfo state, and delete this (S,G) assert 3962 state (action A5 below), and allow the normal PIM Join/Prune 3963 mechanisms to operate. If whoever sent the Join was in error, 3964 then the normal assert mechanism will eventually re-apply and 3965 we will lose the assert again. However whoever sent the 3966 assert may know that the previous assert winner has died, and 3967 so we may end up being the new forwarder. 3969 (S,G) Assert State machine Actions 3971 A1: Send Assert(S,G) 3972 Set Assert Timer to (Assert_Time - Assert_Override_Interval) 3973 Store self as AssertWinner(S,G,I) 3974 Store spt_assert_metric(S,I) as AssertWinnerMetric(S,G,I) 3976 A2: Store new assert winner as AssertWinner(S,G,I) and assert 3977 winner metric as AssertWinnerMetric(S,G,I). 3978 Set Assert Timer to Assert_Time 3980 A3: Send Assert(S,G) 3981 Set Assert Timer to (Assert_Time - Assert_Override_Interval) 3983 A4: Send AssertCancel(S,G) 3984 Delete assert info (AssertWinner(S,G,I) and 3985 AssertWinnerMetric(S,G,I) will then return their default 3986 values). 3988 A5: Delete assert info (AssertWinner(S,G,I) and 3989 AssertWinnerMetric(S,G,I) will then return their default 3990 values). 3992 A6: Store new assert winner as AssertWinner(S,G,I) and assert 3993 winner metric as AssertWinnerMetric(S,G,I). 3994 Set Assert Timer to Assert_Time 3995 If (I is RPF_interface(S)) AND (UpstreamJPState(S,G) == true) 3996 set SPTbit(S,G) to TRUE. 3998 Note that some of these actions may cause the value of JoinDesired(S,G), 3999 PruneDesired(S,G,rpt), or RPF'(S,G) to change, which could cause further 4000 transitions in other state machines. 4002 4.6.2. (*,G) Assert Message State Machine 4004 The (*,G) Assert state machine for interface I is shown in Figure 11. 4005 There are three states: 4007 NoInfo (NI) 4008 This router has no (*,G) assert state on interface I. 4010 I am Assert Winner (W) 4011 This router has won an (*,G) assert on interface I. It is now 4012 responsible for forwarding traffic destined for G onto interface I 4013 with the exception of traffic for which it has (S,G) "I am Assert 4014 Loser" state. Irrespective of whether it is the DR for I, it is 4015 also responsible for handling the membership requests for G from 4016 local hosts on I. 4018 I am Assert Loser (L) 4019 This router has lost an (*,G) assert on interface I. It must not 4020 forward packets for G onto interface I with the exception of 4021 traffic from sources for which is has (S,G) "I am Assert Winner" 4022 state. If it is the DR, it is no longer responsible for handling 4023 the membership requests for group G from local hosts on I. 4025 In addition, there is also an Assert Timer (AT) that is used to time out 4026 asserts on the assert losers and to resend asserts on the assert winner. 4028 When an Assert message is received with a source address other than 4029 zero, a PIM implementation must first match it against the possible 4030 events in the (S,G) assert state machine and process any transitions and 4031 actions, before considering whether the Assert message matches against 4032 the (*,G) assert state machine. 4034 It is important to note that NO TRANSITION CAN OCCUR in the (*,G) state 4035 machine as a result of receiving an Assert message unless the (S,G) 4036 assert state machine for the relevant S and G is in the "NoInfo" state 4037 after the (S,G) state machine has processed the message. Also NO 4038 TRANSITION CAN OCCUR in the (*,G) state machine as a result of receiving 4039 an assert message if that message triggers any change of state in the 4040 (S,G) state machine. Obviously when the source address in the received 4041 message is set to zero an (S,G) state machine for the S and G does not 4042 exist and can be assumed to be in the "NoInfo" state. 4044 For example, if both the (S,G) and (*,G) assert state machines where in 4045 the NoInfo state when an Assert message arrives, and the message causes 4046 the (S,G) state machine to transition to either "W" or "L" state, then 4047 the assert would not be processed by the (*,G) assert state machine. 4049 Another example: if the (S,G) assert state machine is in "L" state when 4050 an assert message is received, and the assert metric in the message is 4051 worse than my_assert_metric(S,G,I), then the (S,G) assert state machine 4052 will transition to NoInfo state. In such a case if the (*,G) assert 4053 state machine were in NoInfo state, it might appear that it would 4054 transition to "W" state, but this is not the case because this message 4055 already triggered a transition in the (S,G) assert state machine. 4057 Figure 11: Per-interface (*,G) Assert State machine in tabular form 4059 F+-----------------------------------------------------------------------+ 4060 | In NoInfo (NI) State | 4061 | 4062 +-----------------------+-----------------------+-----------------------+ 4063 | Receive Inferior | Data arrives for G | Receive Acceptable | 4064 | Assert with RPTbit | on I and | Assert with RPTbit | 4065 | set and | CouldAssert | set and AssTrDes | 4066 | CouldAssert(*,G,I) | (*,G,I) | (*,G,I) | 4067 | 4068 +-----------------------+-----------------------+-----------------------+ 4069 | -> W state | -> W state | -> L state | 4070 | [Actions A1] | [Actions A1] | [Actions A2] | 4071 | 4072 +-----------------------+-----------------------+-----------------------+ 4074 -+-----------------------------------------------------------------------+ 4075 | In I Am Assert Winner (W) State | 4076 | 4077 +----------------+------------------+-----------------+-----------------+ 4078 | Assert Timer | Receive | Receive | CouldAssert | 4079 | Expires | Inferior | Preferred | (*,G,I) -> | 4080 | | Assert | Assert | FALSE | 4081 | 4082 +----------------+------------------+-----------------+-----------------+ 4083 | -> W state | -> W state | -> L state | -> NI state | 4084 | [Actions A3] | [Actions A3] | [Actions A2] | [Actions A4] | 4085 | 4086 +----------------+------------------+-----------------+-----------------+ 4088 -+-------------------------------------------------------------------------+ 4089 | In I Am Assert Loser (L) State | 4090 |+-------------+--------------+--------------+--------------+--------------+ 4091 |Receive | Receive | Receive | Assert Timer | Current | 4092 |Preferred | Acceptable | Inferior | Expires | Winner's | 4093 |Assert | Assert from | Assert from | | GenID | 4094 | | Current | Current | | Changes or | 4095 | | Winner | Winner | | NLT Expires | 4096 |+-------------+--------------+--------------+--------------+--------------+ 4097 |-> L state | -> L state | -> NI state | -> NI state | -> NI state | 4098 |[Actions A2] | [Actions A2] | [Actions A5] | [Actions A5] | [Actions A5] | 4099 A5]+-------------+--------------+--------------+--------------+--------------+ 4100 T+-----------------------------------------------------------------------+ 4101 | In I Am Assert Loser (L) State | 4102 | 4103 +----------------+----------------+------------------+------------------+ 4104 | AssTrDes | my_metric -> | RPF_interface | Receive | 4105 | (*,G,I) -> | better than | (RP(G)) stops | Join(*,G) or | 4106 | FALSE | Winner's | being I | Join | 4107 | | metric | | (*,*,RP(G)) on | 4108 | | | | Interface I | 4109 | 4110 +----------------+----------------+------------------+------------------+ 4111 | -> NI state | -> NI state | -> NI state | -> NI State | 4112 | [Actions A5] | [Actions A5] | [Actions A5] | [Actions A5] | 4113 | 4114 +----------------+----------------+------------------+------------------+ 4116 The state machine uses the following macros: 4118 CouldAssert(*,G,I) = 4119 ( I in ( joins(*,*,RP(G)) (+) joins(*,G) 4120 (+) pim_include(*,G)) ) 4121 AND (RPF_interface(RP(G)) != I) 4123 CouldAssert(*,G,I) is true on downstream interfaces for which we have 4124 (*,*,RP(G)) or (*,G) join state, or local members that requested any 4125 traffic destined for G. 4127 AssertTrackingDesired(*,G,I) = 4128 CouldAssert(*,G,I) 4129 OR (local_receiver_include(*,G,I)==TRUE 4130 AND (I_am_DR(I) OR AssertWinner(*,G,I) == me)) 4131 OR (RPF_interface(RP(G)) == I AND RPTJoinDesired(G)) 4133 AssertTrackingDesired(*,G,I) is true on any interface on which an (*,G) 4134 assert might affect our behavior. 4136 Note that for reasons of compactness, "AssTrDes(*,G,I)" is used in the 4137 state machine table to refer to AssertTrackingDesired(*,G,I). 4139 Terminology: 4140 A "preferred assert" is one with a better metric than the current 4141 winner. 4143 An "acceptable assert" is one that has a better metric than 4144 my_assert_metric(S,G,I). 4146 An "inferior assert" is one with a worse metric than 4147 my_assert_metric(S,G,I). 4149 Transitions from NoInfo State 4151 When in NoInfo state, the following events trigger transitions, but only 4152 if the (S,G) assert state machine is in NoInfo state before and after 4153 consideration of the received message: 4155 Receive Inferior Assert with RPTbit set AND 4156 CouldAssert(*,G,I)==TRUE 4157 An Inferior (*,G) assert is received for G on Interface I. If 4158 CouldAssert(*,G,I) is TRUE, then I is our downstream 4159 interface, and we have (*,G) forwarding state on this 4160 interface, so we should be the assert winner. We transition 4161 to the "I am Assert Winner" state, and perform Actions A1 4162 (below). 4164 A data packet destined for G arrives on interface I, AND 4165 CouldAssert(*,G,I)==TRUE 4166 A data packet destined for G arrived on a downstream interface 4167 which is in our (*,G) outgoing interface list. We therefore 4168 believe we should be the forwarder for this (*,G), and so we 4169 transition to the "I am Assert Winner" state, and perform 4170 Actions A1 (below). 4172 Receive Acceptable Assert with RPT bit set AND 4173 AssertTrackingDesired(*,G,I)==TRUE 4174 We're interested in (*,G) Asserts, either because I is a 4175 downstream interface for which we have (*,G) forwarding state, 4176 or because I is the upstream interface for RP(G) and we have 4177 (*,G) forwarding state. We get a (*,G) Assert that has a 4178 better metric than our own, so we do not win the Assert. We 4179 transition to "I am Assert Loser" and perform actions A2 4180 (below). 4182 Transitions from "I am Assert Winner" State 4184 When in "I am Assert Winner" state, the following events trigger 4185 transitions, but only if the (S,G) assert state machine is in NoInfo 4186 state before and after consideration of the received message: 4188 Receive Inferior Assert 4189 We receive a (*,G) assert that has a worse metric than our 4190 own. Whoever sent the assert has lost, and so we re-send a 4191 (*,G) Assert, and restart the Assert Timer (Action A3 below). 4193 Receive Preferred Assert 4194 We receive a (*,G) assert that has a better metric than our 4195 own. We transition to "I am Assert Loser" state and perform 4196 actions A2 (below). 4198 When in "I am Assert Winner" state, the following events trigger 4199 transitions: 4201 Assert Timer Expires 4202 The (*,G) Assert Timer expires. As we're in the Winner state, 4203 then we must still have (*,G) forwarding state that is 4204 actively being kept alive. To prevent unnecessary thrashing 4205 of the forwarder and periodic flooding of duplicate packets, 4206 we re-send the (*,G) Assert, and restart the Assert Timer 4207 (Action A3 below). 4209 CouldAssert(*,G,I) -> FALSE 4210 Our (*,G) forwarding state or RPF interface changed so as to 4211 make CouldAssert(*,G,I) become false. We can no longer 4212 perform the actions of the assert winner, and so we transition 4213 to NoInfo state and perform actions A4 (below). 4215 Transitions from "I am Assert Loser" State 4217 When in "I am Assert Loser" state, the following events trigger 4218 transitions, but only if the (S,G) assert state machine is in NoInfo 4219 state before and after consideration of the received message: 4221 Receive Preferred Assert 4222 We receive a (*,G) assert that is better than that of the 4223 current assert winner. We stay in Loser state, and perform 4224 actions A2 below. 4226 Receive Acceptable Assert from Current Winner 4227 We receive a (*,G) assert from the current assert winner that 4228 is better than our own metric for this group (although the 4229 metric may be worse than the winner's previous metric). We 4230 stay in Loser state, and perform actions A2 below. 4232 Receive Inferior Assert from Current Winner 4233 We receive an assert from the current assert winner that is 4234 worse than our own metric for this group (typically because 4235 the winner's metric became worse). We transition to NoInfo 4236 state, delete this (*,G) assert state (action A5), and allow 4237 the normal PIM Join/Prune mechanisms to operate. Usually we 4238 will eventually re-assert and win when data packets for G have 4239 started flowing again. 4241 When in "I am Assert Loser" state, the following events trigger 4242 transitions: 4244 Assert Timer Expires 4245 The (*,G) Assert Timer expires. We transition to NoInfo state 4246 and delete this (*,G) assert info (action A5). 4248 Current Winner's GenID Changes or NLT Expires 4249 The Neighbor Liveness Timer associated with the current winner 4250 expires or we receive a Hello message from the current winner 4251 reporting a different GenID from the one it previously 4252 reported. This indicates that the current winner's interface 4253 or router has gone down (and may have come back up), and so we 4254 must assume it no longer knows it was the winner. We 4255 transition to the NoInfo state, deleting the (*,G) assert 4256 information (action A5). 4258 AssertTrackingDesired(*,G,I)->FALSE 4259 AssertTrackingDesired(*,G,I) becomes FALSE. Our forwarding 4260 state has changed so that (*,G) Asserts on interface I are no 4261 longer of interest to us. We transition to NoInfo state and 4262 delete this (*,G) assert info (action A5). 4264 My metric becomes better than the assert winner's metric 4265 My routing metric, rpt_assert_metric(G,I), has changed so that 4266 now my assert metric for (*,G) is better than the metric we 4267 have stored for current assert winner. We transition to 4268 NoInfo state, and delete this (*,G) assert state (action A5), 4269 and allow the normal PIM Join/Prune mechanisms to operate. 4270 Usually we will eventually re-assert and win when data packets 4271 for G have started flowing again. 4273 RPF_interface(RP(G)) stops being interface I 4274 Interface I used to be the RPF interface for RP(G), and now it 4275 is not. We transition to NoInfo state, and delete this (*,G) 4276 assert state (action A5). 4278 Receive Join(*,G) or Join(*,*,RP(G)) on interface I 4279 We receive a Join(*,G) or a Join(*,*,RP(G)) that has the 4280 Upstream Neighbor Address field set to my IP address on 4281 interface I. The action is to transition to NoInfo state, and 4282 delete this (*,G) assert state (action A5), and allow the 4283 normal PIM Join/Prune mechanisms to operate. If whoever sent 4284 the Join was in error, then the normal assert mechanism will 4285 eventually re-apply and we will lose the assert again. 4286 However whoever sent the assert may know that the previous 4287 assert winner has died, and so we may end up being the new 4288 forwarder. 4290 (*,G) Assert State machine Actions 4292 A1: Send Assert(*,G) 4293 Set Assert Timer to (Assert_Time - Assert_Override_Interval) 4294 Store self as AssertWinner(*,G,I). 4295 Store rpt_assert_metric(G,I) as AssertWinnerMetric(*,G,I). 4297 A2: Store new assert winner as AssertWinner(*,G,I) and assert 4298 winner metric as AssertWinnerMetric(*,G,I). 4299 Set Assert Timer to Assert_Time 4301 A3: Send Assert(*,G) 4302 Set Assert Timer to (Assert_Time - Assert_Override_Interval) 4304 A4: Send AssertCancel(*,G) 4305 Delete assert info (AssertWinner(*,G,I) and 4306 AssertWinnerMetric(*,G,I) will then return their default 4307 values). 4309 A5: Delete assert info (AssertWinner(*,G,I) and 4310 AssertWinnerMetric(*,G,I) will then return their default 4311 values). 4313 Note that some of these actions may cause the value of JoinDesired(*,G) 4314 or RPF'(*,G)) to change, which could cause further transitions in other 4315 state machines. 4317 4.6.3. Assert Metrics 4319 Assert metrics are defined as: 4321 struct assert_metric { 4322 rpt_bit_flag; 4323 metric_preference; 4324 route_metric; 4325 ip_address; 4326 }; 4328 When comparing assert_metrics, the rpt_bit_flag, metric_preference, and 4329 route_metric field are compared in order, where the first lower value 4330 wins. If all fields are equal, the primary IP address of the router 4331 that sourced the Assert message is used as a tie-breaker, with the 4332 highest IP address winning. 4334 An assert metric for (S,G) to include in (or compare against) an Assert 4335 message sent on interface I should be computed using the following 4336 pseudocode: 4338 assert_metric 4339 my_assert_metric(S,G,I) { 4340 if( CouldAssert(S,G,I) == TRUE ) { 4341 return spt_assert_metric(S,I) 4342 } else if( CouldAssert(*,G,I) == TRUE ) { 4343 return rpt_assert_metric(G,I) 4344 } else { 4345 return infinite_assert_metric() 4346 } 4347 } 4349 spt_assert_metric(S,I) gives the assert metric we use if we're sending 4350 an assert based on active (S,G) forwarding state: 4352 assert_metric 4353 spt_assert_metric(S,I) { 4354 return {0,MRIB.pref(S),MRIB.metric(S),my_ip_address(I)} 4355 } 4357 rpt_assert_metric(G,I) gives the assert metric we use if we're sending 4358 an assert based only on (*,G) forwarding state: 4360 assert_metric 4361 rpt_assert_metric(G,I) { 4362 return {1,MRIB.pref(RP(G)),MRIB.metric(RP(G)),my_ip_address(I)} 4363 } 4365 MRIB.pref(X) and MRIB.metric(X) are the routing preference and routing 4366 metrics associated with the route to a particular (unicast) destination 4367 X, as determined by the MRIB. my_ip_address(I) is simply the router's 4368 primary IP address that is associated with the local interface I. 4370 infinite_assert_metric() gives the assert metric we need to send an 4371 assert but don't match either (S,G) or (*,G) forwarding state: 4373 assert_metric 4374 infinite_assert_metric() { 4375 return {1,infinity,infinity,0} 4376 } 4378 4.6.4. AssertCancel Messages 4380 An AssertCancel message is simply an RPT Assert message but with 4381 infinite metric. It is sent by the assert winner when it deletes the 4382 forwarding state that had caused the assert to occur. Other routers 4383 will see this metric, and it will cause any other router that has 4384 forwarding state to send its own assert, and to take over forwarding. 4386 An AssertCancel(S,G) is an infinite metric assert with the RPT bit set 4387 that names S as the source. 4389 An AssertCancel(*,G) is an infinite metric assert with the RPT bit set 4390 and the source set to zero. 4392 AssertCancel messages are simply an optimization. The original Assert 4393 timeout mechanism will allow a subnet to eventually become consistent; 4394 the AssertCancel mechanism simply causes faster convergence. No special 4395 processing is required for an AssertCancel message, since it is simply 4396 an Assert message from the current winner. 4398 4.6.5. Assert State Macros 4400 The macros lost_assert(S,G,rpt,I), lost_assert(S,G,I), and 4401 lost_assert(*,G,I) are used in the olist computations of Section 4.1, 4402 and are defined as: 4404 bool lost_assert(S,G,rpt,I) { 4405 if ( RPF_interface(RP(G)) == I OR 4406 ( RPF_interface(S) == I AND SPTbit(S,G) == TRUE ) ) { 4407 return FALSE 4408 } else { 4409 return ( AssertWinner(S,G,I) != NULL AND 4410 AssertWinner(S,G,I) != me ) 4411 } 4412 } 4414 bool lost_assert(S,G,I) { 4415 if ( RPF_interface(S) == I ) { 4416 return FALSE 4417 } else { 4418 return ( AssertWinner(S,G,I) != NULL AND 4419 AssertWinner(S,G,I) != me AND 4420 (AssertWinnerMetric(S,G,I) is better 4421 than spt_assert_metric(S,I) ) 4422 } 4423 } 4425 Note: the term "AssertWinnerMetric(S,G,I) is better than 4426 spt_assert_metric(S,I)" is required to correctly handle the transition 4427 phase when a router has (S,G) join state, but has not yet set the SPT 4428 bit. In this case it needs to ignore the assert state if it will win 4429 the assert once the SPTbit is set. 4431 bool lost_assert(*,G,I) { 4432 if ( RPF_interface(RP(G)) == I ) { 4433 return FALSE 4434 } else { 4435 return ( AssertWinner(*,G,I) != NULL AND 4436 AssertWinner(*,G,I) != me ) 4437 } 4438 } 4440 AssertWinner(S,G,I) is the IP source address of the Assert(S,G) packet 4441 that won an Assert. 4443 AssertWinner(*,G,I) is the IP source address of the Assert(*,G) packet 4444 that won an Assert. 4446 AssertWinnerMetric(S,G,I) is the Assert metric of the Assert(S,G) packet 4447 that won an Assert. 4449 AssertWinnerMetric(*,G,I) is the Assert metric of the Assert(*,G) packet 4450 that won an Assert. 4452 AssertWinner(S,G,I) defaults to NULL and AssertWinnerMetric(S,G,I) 4453 defaults to Infinity when in the NoInfo state. 4455 Summary of Assert Rules and Rationale 4457 This section summarizes the key rules for sending and reacting to 4458 asserts and the rationale for these rules. This section is not intended 4459 to be and should not be treated as a definitive specification of 4460 protocol behavior. The state machines and pseudocode should be 4461 consulted for that purpose. Rather, this section is intended to 4462 document important aspects of a the Assert protocol behavior and to 4463 provide information that may prove helpful to the reader in 4464 understanding and implementing this part of the protocol. 4466 1. Behavior: Downstream neighbors send Join(*,G) and Join(S,G) 4467 periodic messages to the appropriate RPF' neighbor, i.e., the RPF 4468 neighbor as modified by the assert process. They are not always 4469 sent to the RPF neighbor as indicated by the MRIB. Normal 4470 suppression and override rules apply. 4472 Rationale: By sending the periodic and triggered Join messages to 4473 the RPF' neighbor instead of to the RPF neighbor, the downstream 4474 router avoids re-triggering the Assert process with every Join. A 4475 side effect of sending Joins to the Assert winner is that traffic 4476 will not switch back to the "normal" RPF neighbor until the Assert 4477 times out. This will not happen until data stops flowing, if item 4478 8 below is implemented. 4480 2. Behavior: The assert winner for (*,G) acts as the local DR for 4481 (*,G) on behalf of IGMP/MLD members. 4483 Rationale: This is required to allow a single router to merge PIM 4484 and IGMP/MLD joins and leaves. Without this, overrides don't work. 4486 3. Behavior: The assert winner for (S,G) acts as the local DR for 4487 (S,G) on behalf of IGMPv3 members. 4489 Rationale: Same rationale as for 2. 4491 4. Behavior: (S,G) and (*,G) prune overrides are sent to the RPF' 4492 neighbor and not to the regular RPF neighbor. 4494 Rationale: Same as for 1. 4496 5. Behavior: An (S,G,rpt) prune override is not sent (at all) if 4497 RPF'(S,G,rpt) != RPF'(*,G). 4499 Rationale: This avoids keeping state alive on the (S,G) tree when 4500 only (*,G) downstream members are left. Also, it avoids sending 4501 (S,G,rpt) joins to a router that is not on the (*,G) tree. This 4502 behavior might be confusing although this specification does 4503 indicate that such a join should be dropped. 4505 6. Behavior: An assert loser that receives a Join(S,G) with an 4506 Upstream Neighbor Address that is its primary IP address on that | 4507 interface cancels the (S,G) Assert Timer. 4509 Rationale: This is necessary in order to have rapid convergence in 4510 the event that the downstream router that initially sent a join to 4511 the prior Assert winner has undergone a topology change. 4513 7. Behavior: An assert loser that receives a Join(*,G) or a 4514 Join(*,*,RP(G)) with an Upstream Neighbor Address that is one of 4515 its addresses on that interface cancels the (*,G) Assert Timer and 4516 all (S,G) assert timers that do not have corresponding 4517 Prune(S,G,rpt) messages in the compound Join/Prune message. 4519 Rationale: Same as 6. 4521 8. Behavior: An assert winner for (*,G) or (S,G) sends a canceling 4522 assert when it is about to stop forwarding on a (*,G) or an (S,G) 4523 entry. This behavior does not apply to (S,G,rpt). 4525 Rationale: This allows switching back to the shared tree after the 4526 last SPT router on the LAN leaves. Doing this prevents downstream 4527 routers on the shared tree from keeping SPT state alive. 4529 9. Behavior: Re-send the assert messages before timing out an assert. 4530 (This behavior is optional.) 4532 Rationale: This prevents the periodic duplicates that would 4533 otherwise occur each time that an assert times out and is then re- 4534 established. 4536 10. Behavior: When RPF'(S,G,rpt) changes to be the same as RPF'(*,G) we 4537 need to trigger a Join(S,G,rpt) to RPF'(*,G). 4539 Rationale: This allows switching back to the RPT after the last SPT 4540 member leaves. 4542 4.7. PIM Bootstrap and RP Discovery 4544 For correct operation, every PIM router within a PIM domain must be able 4545 to map a particular multicast group address to the same RP. If this is 4546 not the case then black holes may appear, where some receivers in the 4547 domain cannot receive some groups. A domain in this context is a 4548 contiguous set of routers that all implement PIM and are configured to 4549 operate within a common boundary. 4551 A notable exception to this is where a PIM domain is broken up into 4552 multiple administrative scope regions - these are regions where a border 4553 has been configured so that a range of multicast groups will not be 4554 forwarded across that border. For more information on Administratively 4555 Scoped IP Multicast, see RFC 2365. The modified criteria for admin- 4556 scoped regions are that the region is convex with respect to forwarding 4557 based on the MRIB, and that all PIM routers within the scope region map 4558 scoped groups to the same RP within that region. 4560 This specification does not mandate the use of a single mechanism to 4561 provide routers with the information to perform the group-to-RP mapping. 4562 Currently three mechanisms are possible, and all three have associated 4563 problems: 4565 Static Configuration 4566 A PIM router MUST support the static configuration of group-to-RP 4567 mappings. Such a mechanism is not robust to failures, but does at 4568 least provide a basic interoperability mechanism. 4570 Embedded-RP 4571 Embedded-RP defines an address allocation policy in which the 4572 address of the Rendezvous Point (RP) is encoded in an IPv6 4573 multicast group address [15]. 4575 Cisco's Auto-RP 4576 Auto-RP uses a PIM Dense-Mode multicast group to announce group-to- 4577 RP mappings from a central location. This mechanism is not useful 4578 if PIM Dense-Mode is not being run in parallel with PIM Sparse- 4579 Mode, and was only intended for use with PIM Sparse-Mode Version 1. 4580 No standard specification currently exists. 4582 BootStrap Router (BSR) 4583 RFC 2362 specifies a bootstrap mechanism based around the automatic 4584 election of a bootstrap router (BSR). Any router in the domain 4585 that is configured to be a possible RP reports its candidacy to the 4586 BSR, and then a domain-wide flooding mechanism distributes the 4587 BSR's chosen set of RPs throughout the domain. As specified in RFC 4588 2362, BSR is flawed in its handling of admin-scoped regions that 4589 are smaller than a PIM domain, but the mechanism does work for 4590 global-scoped groups. 4592 As far as PIM-SM is concerned, the only important requirement is that 4593 all routers in the domain (or admin scope zone for scoped regions) 4594 receive the same set of group-range-to-RP mappings. This may be 4595 achieved through the use of any of these mechanisms, or through 4596 alternative mechanisms not currently specified. 4598 It must be operationally ensured that any RP address configured, learned 4599 or advertised is reachable from all routers in the PIM domain. 4601 4.7.1. Group-to-RP Mapping 4603 Using one of the mechanisms described above, a PIM router receives one 4604 or more possible group-range-to-RP mappings. Each mapping specifies a 4605 range of multicast groups (expressed as a group and mask) and the RP to 4606 which such groups should be mapped. Each mapping may also have an 4607 associated priority. It is possible to receive multiple mappings all of 4608 which might match the same multicast group - this is the common case 4609 with BSR. The algorithm for performing the group-to-RP mapping is as 4610 follows: 4612 1 Perform longest match on group-range to obtain a list of RPs. 4614 2 From this list of matching RPs, find the one with highest priority. 4615 Eliminate any RPs from the list that have lower priorities. 4617 3 If only one RP remains in the list, use that RP. 4619 4 If multiple RPs are in the list, use the PIM hash function to 4620 choose one. 4622 Thus if two or more group-range-to-RP mappings cover a particular group, 4623 the one with the longest mask is the mapping to use. If the mappings 4624 have the same mask length, then the one with the highest priority is 4625 chosen. If there is more than one matching entry with the same longest 4626 mask and the priorities are identical, then a hash function (see Section 4627 4.7.2) is applied to choose the RP. 4629 This algorithm is invoked by a DR when it needs to determine an RP for a 4630 given group, e.g. upon reception of a packet or IGMP/MLD membership 4631 indication for a group for which the DR does not know the RP. It is 4632 invoked by any router that has (*,*,RP) state when a packet is received 4633 for which there is no corresponding (S,G) or (*,G) entry. Furthermore, 4634 the mapping function is invoked by all routers upon receiving a (*,G) or 4635 (*,*,RP) Join/Prune message. 4637 Note that if the set of possible group-range-to-RP mappings changes, 4638 each router will need to check whether any existing groups are affected. 4639 This may, for example, cause a DR or acting DR to re-join a group, or 4640 cause it to re-start register encapsulation to the new RP. 4642 Implementation note: the bootstrap mechanism described in RFC 4643 2362 omitted step (1) above. However of the implementations 4644 we are aware of, approximately half performed step (1) anyway. 4645 It should be noted that implementations of BSR that omit step 4646 1 will not correctly interoperate with implementations of this 4647 specification when used with the BSR mechanism described in 4648 [11]. 4650 4.7.2. Hash Function 4652 The hash function is used by all routers within a domain, to map a group 4653 to one of the RPs from the matching set of group-range-to-RP mappings 4654 (this set all have the same longest mask length and same highest 4655 priority). The algorithm takes as input the group address, and the 4656 addresses of the candidate RPs from the mappings, and gives as output 4657 one RP address to be used. 4659 The protocol requires that all routers hash to the same RP within a 4660 domain (except for transients). The following hash function must be used 4661 in each router: 4663 1 For RP addresses in the matching group-range-to-RP mappings, 4664 compute a value: 4666 Value(G,M,C(i))= 4667 (1103515245 * ((1103515245 * (G&M)+12345) XOR C(i)) + 12345) mod 2^31 4669 where C(i) is the RP address and M is a hash-mask. If BSR is being 4670 used, the hash-mask is given in the Bootstrap messages. If BSR is 4671 not being used, the alternative mechanism that supplies the group- 4672 range-to-RP mappings may supply the value, or else it defaults to a 4673 mask with the most significant 30 bits being one for IPv4 and the 4674 most significant 126 bits being one for IPv6. The hash-mask allows 4675 a small number of consecutive groups (e.g., 4) to always hash to 4676 the same RP. For instance, hierarchically-encoded data can be sent 4677 on consecutive group addresses to get the same delay and fate- 4678 sharing characteristics. 4680 For address families other than IPv4, a 32-bit digest to be used as 4681 C(i) and G must first be derived from the actual RP or group 4682 address. Such a digest method must be used consistently throughout 4683 the PIM domain. For IPv6 addresses, we recommend using the 4684 equivalent IPv4 address for an IPv4-compatible address, and the 4685 exclusive-or of each 32-bit segment of the address for all other 4686 IPv6 addresses. For example, the digest of the IPv6 address 4687 3ffe:b00:c18:1::10 would be computed as 0x3ffe0b00 ^ 0x0c180001 ^ 4688 0x00000000 ^ 0x00000010, where ^ represents the exclusive-or 4689 operation. 4691 2 The candidate RP with the highest resulting hash value is then the 4692 RP chosen by this Hash Function. If more than one RP has the same 4693 highest hash value, the RP with the highest IP address is chosen. 4695 4.8. Source-Specific Multicast 4697 The Source-Specific Multicast (SSM) service model [5] can be implemented 4698 with a strict subset of the PIM-SM protocol mechanisms. Both regular IP 4699 Multicast and SSM semantics can coexist on a single router and both can 4700 be implemented using the PIM-SM protocol. A range of multicast 4701 addresses, currently 232.0.0.0/8 in IPv4 and FF3x::/32 for IPv6, is 4702 reserved for SSM, and the choice of semantics is determined by the 4703 multicast group address in both data packets and PIM messages. 4705 4.8.1. Protocol Modifications for SSM destination addresses 4707 The following rules override the normal PIM-SM behavior for a multicast 4708 address G in the SSM range: 4710 o A router MUST NOT send a (*,G) Join/Prune message for any reason. 4712 o A router MUST NOT send an (S,G,rpt) Join/Prune message for any reason. 4714 o A router MUST NOT send a Register message for any packet that is 4715 destined to an SSM address. 4717 o A router MUST NOT forward packets based on (*,G) or (S,G,rpt) state. 4718 The (*,G) and (S,G,rpt) -related state summarization macros are NULL 4719 for any SSM address, for the purposes of packet forwarding. 4721 o A router acting as an RP MUST NOT forward any Register-encapsulated 4722 packet that has an SSM destination address. 4724 The last two rules are present to deal with "legacy" routers unaware of 4725 SSM that may be sending (*,G) and (S,G,rpt) Join/Prunes, or Register 4726 messages for SSM destination addresses. 4728 Additionally: 4730 o A router MAY be configured to advertise itself as a Candidate RP for 4731 an SSM address. If so, it SHOULD respond with a Register-Stop message 4732 to any Register message containing a packet destined for an SSM 4733 address. 4735 o A router MAY optimize out the creation and maintenance of (S,G,rpt) 4736 and (*,G) state for SSM destination addresses -- this state is not 4737 needed for SSM packets. 4739 4.8.2. PIM-SSM-only Routers 4741 An implementor may choose to implement only the subset of PIM Sparse- 4742 Mode that provides SSM forwarding semantics. 4744 A PIM-SSM-only router MUST implement the following portions of this 4745 specification: 4747 o Upstream (S,G) state machine (Section 4.5.7) 4749 o Downstream (S,G) state machine (Section 4.5.3) 4751 o (S,G) Assert state machine (Section 4.6.1) 4753 o Hello messages, neighbor discovery and DR election (Section 4.3) 4755 o Packet forwarding rules (Section 4.2) 4756 A PIM-SSM-only router does not need to implement the following protocol 4757 elements: 4759 o Register state machine (Section 4.4) 4761 o (*,G), (S,G,rpt) and (*,*,RP) Downstream state machines (Sections 4762 4.5.2, 4.5.4, and 4.5.1) 4764 o (*,G), (S,G,rpt), and (*,*,RP) Upstream state machines (Sections 4765 4.5.6, 4.5.8, and 4.5.5) 4767 o (*,G) Assert state machine (Section 4.6.2) 4769 o Bootstrap RP Election (Section 4.7) 4771 o Keepalive Timer 4773 o SptBit (Section 4.2.2) 4775 The Keepalive Timer should be treated as always running and SptBit 4776 should be treated as being always set for an SSM address. Additionally, 4777 the Packet forwarding rules of Section 4.2 can be simplified in a PIM- 4778 SSM-only router: 4780 if( iif == RPF_interface(S) AND UpstreamJPState(S,G) == Joined ) { 4781 oiflist = inherited_olist(S,G) 4782 } else if( iif is in inherited_olist(S,G) ) { 4783 send Assert(S,G) on iif 4784 } 4786 oiflist = oiflist (-) iif 4787 forward packet on all interfaces in oiflist 4789 This is nothing more than the reduction of the normal PIM-SM forwarding 4790 rule, with all (S,G,rpt) and (*,G) clauses replaced with NULL. 4792 4.9. PIM Packet Formats 4794 This section describes the details of the packet formats for PIM control 4795 messages. 4797 All PIM control messages have IP protocol number 103. 4799 PIM messages are either unicast (e.g. Registers and Register-Stop), or 4800 multicast with TTL 1 to the `ALL-PIM-ROUTERS' group (e.g. Join/Prune, 4801 Asserts, etc.). The source address used for unicast messages is a 4802 domain-wide reachable address; the source address used for multicast 4803 messages is the link-local address of the interface on which the message 4804 is being sent. 4806 The IPv4 `ALL-PIM-ROUTERS' group is `224.0.0.13'. The IPv6 `ALL-PIM- 4807 ROUTERS' group is `ff02::d'. 4809 The PIM header common to all PIM messages is: 4811 0 1 2 3 4812 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 4813 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4814 |PIM Ver| Type | Reserved | Checksum | 4815 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4817 PIM Ver 4818 PIM Version number is 2. 4820 Type Types for specific PIM messages. PIM Types are: 4822 Message Type Destination 4823 Mes--------------------------------------------------------------------------- 4824 0 = Hello Multicast to ALL-PIM-ROUTERS 4825 1 = Register Unicast to RP 4826 2 = Register-Stop Unicast to source of Register packet 4827 3 = Join/Prune Multicast to ALL-PIM-ROUTERS 4828 4 = Bootstrap Multicast to ALL-PIM-ROUTERS 4829 5 = Assert Multicast to ALL-PIM-ROUTERS 4830 6 = Graft (used in PIM-DM only) Multicast to ALL-PIM-ROUTERS 4831 7 = Graft-Ack (used in PIM-DM only) Unicast to source of Graft packet 4832 8 = Candidate-RP-Advertisement Unicast to Domain's BSR 4834 Reserved 4835 Set to zero on transmission. Ignored upon receipt. 4837 Checksum 4838 The checksum is a standard IP checksum, i.e. the 16-bit one's 4839 complement of the one's complement sum of the entire PIM message, 4840 excluding the "Multicast data packet" section of the Register 4841 message. For computing the checksum, the checksum field is zeroed. 4842 If the packet's length is not an integral number of 16-bit words, 4843 the packet is padded with a trailing byte of zero before performing 4844 the checksum. 4846 For IPv6, the checksum also includes the IPv6 "pseudo-header", as 4847 specified in RFC 2460, Section 8.1 [4]. This "pseudo-header" is 4848 prepended to the PIM header for the purposes of calculating the 4849 checksum. The "Upper-Layer Packet Length" in the pseudo-header is 4850 set to the length of the PIM message, except in Register messages 4851 where it is set to the length of the PIM register header (8). The 4852 Next Header value used in the pseudo-header is 103. 4854 If a message is received with an unrecognized PIM Ver or Type field or a 4855 message's destination does not correspond to the table above, it MUST be 4856 discarded and an error message SHOULD be logged to the administrator in 4857 a rate limited manner. 4859 4.9.1. Encoded Source and Group Address Formats 4861 Encoded-Unicast address 4863 An Encoded-Unicast address takes the following format: 4865 0 1 2 3 4866 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 4867 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4868 | Addr Family | Encoding Type | Unicast Address 4869 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+... 4871 Addr Family 4872 The PIM address family of the `Unicast Address' field of this 4873 address. 4875 Values of 0-127 are as assigned by the IANA for Internet Address 4876 Families in [6]. Values 128-250 are reserved to be assigned by the 4877 IANA for PIM-specific Address Families. Values 251 though 255 are 4878 designated for private use. As there is no assignment authority 4879 for this space, collisions should be expected. 4881 Encoding Type 4882 The type of encoding used within a specific Address Family. The 4883 value `0' is reserved for this field, and represents the native 4884 encoding of the Address Family. 4886 Unicast Address 4887 The unicast address as represented by the given Address Family and 4888 Encoding Type. 4890 Encoded-Group address 4892 Encoded-Group addresses take the following format: 4894 0 1 2 3 4895 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 4896 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4897 | Addr Family | Encoding Type |B| Reserved |Z| Mask Len | 4898 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4899 | Group multicast Address 4900 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+... 4902 Addr Family 4903 described above. 4905 Encoding Type 4906 described above. 4908 [B]idirectional PIM 4909 indicates the group range should use Bidirectional PIM [12]. For 4910 PIM-SM defined in this specification, this bit MUST be zero. 4912 Reserved 4913 Transmitted as zero. Ignored upon receipt. 4915 Admin Scope [Z]one 4916 indicates the group range is an admin scope zone. This is used in 4917 the Bootstrap Router Mechanism [11] only. For all other purposes, 4918 this bit is set to zero and ignored on receipt. 4920 Mask Len 4921 The Mask length field is 8 bits. The value is the number of 4922 contiguous one bits left justified used as a mask which, combined 4923 with the group address, describes a range of groups. It is less 4924 than or equal to the address length in bits for the given Address 4925 Family and Encoding Type. If the message is sent for a single group 4926 then the Mask length must equal the address length in bits for the 4927 given Address Family and Encoding Type. (e.g. 32 for IPv4 native 4928 encoding, 128 for IPv6 native encoding). 4930 Group multicast Address 4931 Contains the group address. 4933 Encoded-Source address 4935 Encoded-Source address takes the following format: 4937 0 1 2 3 4938 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 4939 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4940 | Addr Family | Encoding Type | Rsrvd |S|W|R| Mask Len | 4941 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4942 | Source Address 4943 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-... 4945 Addr Family 4946 described above. 4948 Encoding Type 4949 described above. 4951 Reserved 4952 Transmitted as zero, ignored on receipt. 4954 S The Sparse bit is a 1 bit value, set to 1 for PIM-SM. It is used 4955 for PIM version 1 compatibility. 4957 W The WC (or WildCard) bit is a 1 bit value for use with PIM 4958 Join/Prune messages (see Section 4.9.5.1 ). 4960 R The RPT (or Rendezvous Point Tree) bit is a 1 bit value for use 4961 with PIM Join/Prune messages (see Section 4.9.5.1 ). If the WC bit 4962 is 1, the RPT bit MUST be 1. 4964 Mask Len 4965 The mask length field is 8 bits. The value is the number of 4966 contiguous one bits left justified used as a mask which, combined 4967 with the Source Address, describes a source subnet. The mask length 4968 MUST be equal to the mask length in bits for the given Address 4969 Family and Encoding Type (32 for IPv4 native and 128 for IPv6 4970 native). A router SHOULD ignore any messages received with any 4971 other mask length. 4973 Source Address 4974 The source address. 4976 4.9.2. Hello Message Format 4978 It is sent periodically by routers on all interfaces. 4980 0 1 2 3 4981 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 4982 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4983 |PIM Ver| Type | Reserved | Checksum | 4984 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4985 | OptionType | OptionLength | 4986 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4987 | OptionValue | 4988 | ... | 4989 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4990 | . | 4991 | . | 4992 | . | 4993 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4994 | OptionType | OptionLength | 4995 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4996 | OptionValue | 4997 | ... | 4998 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5000 PIM Version, Type, Reserved, Checksum 5001 Described in Section 4.9. 5003 OptionType 5004 The type of the option given in the following OptionValue field. 5006 OptionLength 5007 The length of the OptionValue field in bytes. 5009 OptionValue 5010 A variable length field, carrying the value of the option. 5012 The Option fields may contain the following values: 5014 o OptionType 1: Holdtime 5016 0 1 2 3 5017 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 5018 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5019 | Type = 1 | Length = 2 | 5020 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5021 | Holdtime | 5022 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5024 Holdtime is the amount of time a receiver must keep the neighbor 5025 reachable, in seconds. If the Holdtime is set to `0xffff', the 5026 receiver of this message never times out the neighbor. This may 5027 be used with dial-on-demand links, to avoid keeping the link up 5028 with periodic Hello messages. 5030 Hello messages with a Holdtime value set to `0' are also sent by 5031 a router on an interface about to go down or changing IP address 5032 (see Section 4.3.1). These are effectively goodbye messages and 5033 the receiving routers should immediately time out the neighbor 5034 information for the sender. 5036 o OptionType 2: LAN Prune Delay 5038 0 1 2 3 5039 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 5040 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5041 | Type = 2 | Length = 4 | 5042 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5043 |T| Propagation_Delay | Override_Interval | 5044 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5046 The LAN Prune Delay option is used to tune the prune propagation 5047 delay on multi-access LANs. The T bit specifies the ability of 5048 the sending router to disable joins suppression. 5049 Propagation_Delay and Override_Interval are time intervals in 5050 units of milliseconds. A router originating a LAN Prune Delay 5051 option on interface I sets the Propagation_Delay field to the 5052 configured value of Propagation_Delay(I) and the value of the 5053 Override_Interval field to the value of Override_Interval(I). On 5054 a receiving router the values of the fields are used to tune the 5055 value of the Effective_Override_Interval(I) and its derived timer 5056 values. Section 4.3.3 describes how these values affect the 5057 behavior of a router. 5059 o OptionType 3 to 16: reserved to be defined in future versions of 5060 this document. 5062 o OptionType 18: deprecated and should not be used. 5064 o OptionType 19: DR Priority 5066 0 1 2 3 5067 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 5068 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5069 | Type = 19 | Length = 4 | 5070 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5071 | DR Priority | 5072 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5074 DR Priority is a 32-bit unsigned number and should be considered 5075 in the DR election as described in Section 4.3.2. 5077 o OptionType 20: Generation ID 5079 0 1 2 3 5080 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 5081 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5082 | Type = 20 | Length = 4 | 5083 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5084 | Generation ID | 5085 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5087 Generation ID is a random 32-bit value for the interface on which 5088 the Hello message is sent. The Generation ID is regenerated 5089 whenever PIM forwarding is started or restarted on the interface. 5091 o OptionType 24: Address List 5093 0 1 2 3 5094 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 5095 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5096 | Type = 24 | Length = | 5097 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5098 | Secondary Address 1 (Encoded-Unicast format) | 5099 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5100 ... 5101 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5102 | Secondary Address N (Encoded-Unicast format) | 5103 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5105 The contents of the Address List Hello option are described in 5106 Section 4.3.4. All addresses within a single Address List must 5107 belong to the same address family. 5109 OptionTypes 17 thru 65000 are assigned by the IANA. OptionTypes 5110 65001 through 65535 are reserved for Private Use, as defined in 5111 [8]. 5112 Unknown options MUST be ignored, and MUST NOT prevent a neighbor | 5113 relationship from being formed. The "Holdtime" option MUST be 5114 implemented; the "DR Priority" and "Generation ID" options SHOULD 5115 be implemented. The "Address List" option MUST be implemented for 5116 IPv6. 5118 4.9.3. Register Message Format 5120 A Register message is sent by the DR or a PMBR to the RP when a 5121 multicast packet needs to be transmitted on the RP-tree. The IP source 5122 address is set to the address of the DR, the destination address to the 5123 RP's address. The IP TTL of the PIM packet is the system's normal 5124 unicast TTL. 5126 0 1 2 3 5127 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 5128 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5129 |PIM Ver| Type | Reserved | Checksum | 5130 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5131 |B|N| Reserved2 | 5132 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5133 | | 5134 . Multicast data packet . 5135 | | 5136 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5138 PIM Version, Type, Reserved, Checksum 5139 Described in Section 4.9. Note that in order to reduce 5140 encapsulation overhead, the checksum for Registers is done only on 5141 first 8 bytes of the packet, including the PIM header and the next 5142 4 bytes, excluding the data packet portion. For interoperability 5143 reasons, a message carrying a checksum calculated over the entire 5144 PIM Register message should also be accepted. When calculating the 5145 checksum, the IPv6 pseudoheader "Upper-Layer Packet Length" is set 5146 to 8. 5148 B The Border bit. If the router is a DR for a source that it is 5149 directly connected to, it sets the B bit to 0. If the router is a 5150 PMBR for a source in a directly connected cloud, it sets the B bit 5151 to 1. 5153 N The Null-Register bit. Set to 1 by a DR that is probing the RP 5154 before expiring its local Register-Suppression Timer. Set to 0 5155 otherwise. 5157 Reserved2 5158 Transmitted as zero, ignored on receipt. 5160 Multicast data packet 5161 The original packet sent by the source. This packet must be of the 5162 same address family as the encapsulating PIM packet, e.g. an IPv6 5163 data packet must be encapsulated in an IPv6 PIM packet. Note that 5164 the TTL of the original packet is decremented before encapsulation, 5165 just like any other packet that is forwarded. In addition, the RP 5166 decrements the TTL after decapsulating, before forwarding the 5167 packet down the shared tree. 5169 For (S,G) Null-Registers, the Multicast data packet portion 5170 contains a dummy IP header with S as the source address, G as the 5171 destination address. When generating an IPv4 Null-Register 5172 message, the fields in the dummy IPv4 header SHOULD be filled in 5173 according to the following table. Other IPv4 header fields may 5174 contain any value that is valid for that field. 5176 Field Value 5177 --------------------------------------- 5178 IP Version 4 5179 Header Length 5 5180 Checksum Header checksum 5181 Fragmentation offset 0 5182 More Fragments 0 5183 Total Length 20 5184 IP Protocol 103 (PIM) 5186 On receipt of an (S,G) Null-Register, if the Header Checksum field 5187 is non-zero, the recipient SHOULD check the checksum and discard 5188 null registers that have a bad checksum. The recipient SHOULD NOT 5189 check the value of any individual fields; a correct IP header 5190 checksum is sufficient. If the Header Checksum field is zero, the 5191 recipient MUST NOT check the checksum. 5193 With IPv6, an implementation generates a dummy IP header followed 5194 by a dummy PIM header with values according to the following table 5195 in addition to the source and group. Other IPv6 header fields may 5196 contain any value that is valid for that field. 5198 Header Field Value 5199 -------------------------------------- 5200 IP Version 6 5201 Next Header 103 (PIM) 5202 Length 4 5203 PIM Version 0 5204 PIM Type 0 5205 PIM Reserved 0 5206 PIM Checksum PIM checksum including 5207 IPv6 "pseudo-header"; 5208 see Section 4.9 5210 On receipt of an IPv6 (S,G) Null-Register, if the dummy PIM header 5211 is present, the recipient SHOULD check the checksum and discard 5212 Null-Registers that have a bad checksum. 5214 4.9.4. Register-Stop Message Format 5216 A Register-Stop is unicast from the RP to the sender of the Register 5217 message. The IP source address is the address to which the register was 5218 addressed. The IP destination address is the source address of the 5219 register message. 5221 0 1 2 3 5222 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 5223 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5224 |PIM Ver| Type | Reserved | Checksum | 5225 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5226 | Group Address (Encoded-Group format) | 5227 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5228 | Source Address (Encoded-Unicast format) | 5229 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5231 PIM Version, Type, Reserved, Checksum 5232 Described in Section 4.9. 5234 Group Address 5235 The group address from the multicast data packet in the Register. 5236 Format described in Section 4.9.1. Note that for Register-Stops the 5237 Mask Len field contains the full address length * 8 (e.g. 32 for 5238 IPv4 native encoding), if the message is sent for a single group. 5240 Source Address 5241 The host address of the source from the multicast data packet in 5242 the register. The format for this address is given in the Encoded- 5243 Unicast address in Section 4.9.1. A special wild card value 5244 consisting of an address field of all zeroes can be used to 5245 indicate any source. 5247 4.9.5. Join/Prune Message Format 5249 A Join/Prune message is sent by routers towards upstream sources and 5250 RPs. Joins are sent to build shared trees (RP trees) or source trees 5251 (SPT). Prunes are sent to prune source trees when members leave groups 5252 as well as sources that do not use the shared tree. 5254 0 1 2 3 5255 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 5256 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5257 |PIM Ver| Type | Reserved | Checksum | 5258 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5259 | Upstream Neighbor Address (Encoded-Unicast format) | 5260 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5261 | Reserved | Num groups | Holdtime | 5262 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5263 | Multicast Group Address 1 (Encoded-Group format) | 5264 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5265 | Number of Joined Sources | Number of Pruned Sources | 5266 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5267 | Joined Source Address 1 (Encoded-Source format) | 5268 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5269 | . | 5270 | . | 5271 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5272 | Joined Source Address n (Encoded-Source format) | 5273 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5274 | Pruned Source Address 1 (Encoded-Source format) | 5275 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5276 | . | 5277 | . | 5278 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5279 | Pruned Source Address n (Encoded-Source format) | 5280 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5281 | . | 5282 | . | 5283 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5284 | Multicast Group Address m (Encoded-Group format) | 5285 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5286 | Number of Joined Sources | Number of Pruned Sources | 5287 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5288 | Joined Source Address 1 (Encoded-Source format) | 5289 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5290 | . | 5291 | . | 5292 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5293 | Joined Source Address n (Encoded-Source format) | 5294 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5295 | Pruned Source Address 1 (Encoded-Source format) | 5296 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5297 | . | 5298 | . | 5299 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5300 | Pruned Source Address n (Encoded-Source format) | 5301 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5302 PIM Version, Type, Reserved, Checksum 5303 Described in Section 4.9. 5305 Unicast Upstream Neighbor Address 5306 The address of the upstream neighbor that is the target of the 5307 message. The format for this address is given in the Encoded- 5308 Unicast address in Section 4.9.1. For IPv6 the source address used 5309 for multicast messages is the link-local address of the interface 5310 on which the message is being sent. For IPv4, the source address 5311 is the primary address associated with that interface. 5313 Reserved 5314 Transmitted as zero, ignored on receipt. 5316 Holdtime 5317 The amount of time a receiver must keep the Join/Prune state alive, 5318 in seconds. If the Holdtime is set to `0xffff', the receiver of 5319 this message should hold the state until canceled by the 5320 appropriate canceling Join/Prune message, or timed out according to 5321 local policy. This may be used with dial-on-demand links, to avoid 5322 keeping the link up with periodic Join/Prune messages. 5324 Note that the HoldTime must be larger than the 5325 J/P_Override_Interval(I). 5327 Number of Groups 5328 The number of multicast group sets contained in the message. 5330 Multicast group address 5331 For format description see Section 4.9.1. 5333 Number of Joined Sources 5334 Number of join source addresses listed for a given group. 5336 Join Source Address 1 .. n 5337 This list contains the sources that the sending router will forward 5338 multicast datagrams for if received on the interface this message 5339 is sent on. 5341 See Encoded-Source-Address format in Section 4.9.1. 5343 Number of Pruned Sources 5344 Number of prune source addresses listed for a group. 5346 Prune Source Address 1 .. n 5347 This list contains the sources that the sending router does not 5348 want to forward multicast datagrams for when received on the 5349 interface this message is sent on. 5351 Within one PIM Join/Prune message, all the Multicast Group Addresses, 5352 Joined Source addresses and Pruned Source addresses MUST be of the same 5353 address family. It is NOT PERMITTED to mix IPv4 and IPv6 addresses 5354 within the same message. In addition, the address family of the fields 5355 in the message SHOULD be the same as the IP source and destination 5356 addresses of the packet. This permits maximum implementation 5357 flexibility for dual-stack IPv4/IPv6 routers. If a router receives a 5358 message with mixed family addresses, it SHOULD only process the 5359 addresses which are of the same family as the unicast upstream neighbor 5360 address. 5362 4.9.5.1. Group Set Source List Rules 5364 As described above, Join / Prune messages are composed of one or more 5365 group sets. Each set contains two source lists, the Join Sources and the 5366 Prune Sources. This section describes the different types of group sets 5367 and source list entries that can exist in a Join / Prune message. 5369 There are two valid group set types: 5371 Wildcard Group Set 5372 The wildcard group set is represented by the entire multicast range 5373 - the beginning of the multicast address range in the group address 5374 field and the prefix length of the multicast address range in the 5375 mask length field of the Multicast Group Address, i.e., 5376 `224.0.0.0/4' for IPv4 or `ff00::/8' for IPv6. Each Join / Prune | 5377 message SHOULD contain at most one wildcard group set. Each 5378 wildcard group set may contain one or more (*,*,RP) source list 5379 entries in either the Join or Prune lists. 5381 A (*,*,RP) source list entry may only exist in a wildcard group 5382 set. When added to a Join source list, this type of source entry 5383 expresses the router's interest in receiving traffic for all groups 5384 mapping to the specified RP. When added to a Prune source list a 5385 (*,*,RP) entry expresses the router's interest to stop receiving 5386 such traffic. Note that as indicated by the Join/Prune state 5387 machines, such a Join or Prune will NOT override Join/Prune state 5388 created using a Group-Specific Set (see below). 5390 (*,*,RP) source list entries have the Source-Address set to the 5391 address of the RP, the Source-Address Mask-Len set to the full 5392 length of the IP address and both the WC and RPT bits of the 5393 Source-Address set to 1. 5395 Group Specific Set 5396 A Group Specific Set is represented by a valid IP multicast address 5397 in the group address field and the full length of the IP address in | 5398 the mask length field of the Multicast Group Address. Each Join / | 5399 Prune message SHOULD NOT contain more than one group specific set | 5400 for the same IP multicast address. Each group specific set may 5401 contain (*,G), (S,G,rpt) and (S,G) source list entries in the Join 5402 or Prune lists. 5404 (*,G) 5405 The (*,G) source list entry is used in Join / Prune messages 5406 sent towards the RP for the specified group. It expresses 5407 interest (or lack of) in receiving traffic sent to the group 5408 through the Rendezvous-Point shared tree. There may only be 5409 one such entry in both the Join and Prune lists of a group 5410 specific set. 5412 (*,G) source list entries have the Source-Address set to the 5413 address of the RP for group G, the Source-Address Mask-Len set 5414 to the full length of the IP address and have both the WC and 5415 RPT bits of the Encoded-Source-Address set. 5417 (S,G,rpt) 5418 The (S,G,rpt) source list entry is used in Join / Prune 5419 messages sent towards the RP for the specified group. It 5420 expresses interest (or lack of) in receiving traffic through 5421 the shared tree sent by the specified source to this group. 5422 For each source address the entry may exist in only one of the 5423 Join and Prune source lists of a group specific set but not 5424 both. 5426 (S,G,rpt) source list entries have the Source-Address set to 5427 the address of the source S, the Source-Address Mask-Len set 5428 to the full length of the IP address and have the WC bit clear 5429 and the RPT bit set in the Encoded-Source-Address. 5431 (S,G) 5432 The (S,G) source list entry is used in Join / Prune messages 5433 sent towards the specified source. It expresses interest (or 5434 lack of) in receiving traffic through the shortest path tree 5435 sent by the source to the specified group. For each source 5436 address the entry may exist in only one of the Join and Prune 5437 source lists of a group specific set but not both. 5439 (S,G) source list entries have the Source-Address set to the 5440 address of the source S, the Source-Address Mask-Len set to 5441 the full length of the IP address and have both the WC and RPT 5442 bits of the Encoded-Source-Address cleared. 5444 The rules described above are sufficient to prevent invalid combinations 5445 of source list entries in group-specific sets. There are however a 5446 number of combinations that have a valid interpretation but which are 5447 not generated by the protocol as described in this specification: 5449 o Combining a (*,G) Join and a (S,G,rpt) Join entry in the same message 5450 is redundant as the (*,G) entry covers the information provided by the 5451 (S,G,rpt) entry. 5453 o The same applies for a (*,G) Prunes and (S,G,rpt) Prunes. 5455 o The combination of a (*,G) Prune and a (S,G,rpt) Join is also not 5456 generated. (S,G,rpt) Joins are only sent when the router is receiving 5457 all traffic for a group on the shared tree and it wishes to indicate a 5458 change for the particular source. As a (*,G) prune indicates that the 5459 router no longer wishes to receive shared tree traffic, the (S,G,rpt) 5460 Join would be meaningless. 5462 o As Join / Prune messages are targeted to a single PIM neighbor, 5463 including both a (S,G) Join and a (S,G,rpt) Prune in the same message 5464 is redundant. The (S,G) Join informs the neighbor that the sender 5465 wishes to receive the particular source on the shortest path tree. It 5466 is therefore unnecessary for the router to say that it no longer 5467 wishes to receive it on the shared tree. 5469 o The combination of a (S,G) Prune and a (S,G,rpt) Join could possibly 5470 be used by a router to switch from receiving a particular source on 5471 the shortest-path tree back to receiving it on the shared tree 5472 (provided that the RPF neighbor for the shortest-path and shared trees 5473 is common). However Sparse-Mode PIM does not provide a mechanism for 5474 switching back to the shared tree. 5476 The rules are summarized in the tables below. 5478 +----------++------+-------+-----------+-----------+-------+-------+ 5479 | ||Join | Prune | Join | Prune | Join | Prune | 5480 | ||(*,G) | (*,G) | (S,G,rpt) | (S,G,rpt) | (S,G) | (S,G) | 5481 +----------++------+-------+-----------+-----------+-------+-------+ 5482 |Join ||- | no | ? | yes | yes | yes | 5483 |(*,G) || | | | | | | 5484 +----------++------+-------+-----------+-----------+-------+-------+ 5485 |Prune ||no | - | ? | ? | yes | yes | 5486 |(*,G) || | | | | | | 5487 +----------++------+-------+-----------+-----------+-------+-------+ 5488 |Join ||? | ? | - | no | yes | ? | 5489 |(S,G,rpt) || | | | | | | 5490 +----------++------+-------+-----------+-----------+-------+-------+ 5491 |Prune ||yes | ? | no | - | ? | yes | 5492 |(S,G,rpt) || | | | | | | 5493 +----------++------+-------+-----------+-----------+-------+-------+ 5494 |Join ||yes | yes | yes | ? | - | no | 5495 |(S,G) || | | | | | | 5496 +----------++------+-------+-----------+-----------+-------+-------+ 5497 |Prune ||yes | yes | yes | ? | no | - | 5498 |(S,G) || | | | | | | 5499 +----------++------+-------+-----------+-----------+-------+-------+ 5501 +---------------++--------------+----------------+------------+ 5502 | ||Join (*,*,RP) | Prune (*,*,RP) | all others | 5503 +---------------++--------------+----------------+------------+ 5504 |Join (*,*,RP) ||- | no | yes | 5505 +---------------++--------------+----------------+------------+ 5506 |Prune (*,*,RP) ||no | - | yes | 5507 +---------------++--------------+----------------+------------+ 5508 |all others ||yes | yes | see above | 5509 +---------------++--------------+----------------+------------+ 5511 yes Allowed and expected. 5513 no Combination is not allowed by the protocol and MUST NOT be 5514 generated by a router. A router MAY accept these messages but the 5515 result is undefined. An error message MAY be logged to the 5516 administrator in a rate limited manner. 5518 ? Combination not expected by the protocol, but well-defined. A 5519 router MAY accept it but SHOULD NOT generate it. 5521 The order of source list entries in a group set source list is not 5522 important, except where limited by the packet format itself. 5524 4.9.5.2. Group Set Fragmentation 5526 When building a Join / Prune for a particular neighbor, a router should 5527 try and include in the message as much of the information it needs to 5528 convey to the neighbor as possible. This implies adding one group set 5529 for each multicast group that has information pending transmission and 5530 within each set including all relevant source list entries. 5532 On a router with a large amount of multicast state the number of entries 5533 that must be included may result in packets that are larger than the 5534 maximum IP packet size. In most such cases the information may be split 5535 into multiple messages. 5537 There is an exception with group sets that contain a (*,G) Join source 5538 list entry. The group set expresses the router's interest in receiving 5539 all traffic for the specified group on the shared tree and it MUST 5540 include an (S,G,rpt) Prune source list entry for every source that the 5541 router does not wish to receive. This list of (S,G,rpt) Prune source- 5542 list entries MUST not be split in multiple messages. 5544 If only N (S,G,rpt) Prune entries fit into a maximum-sized Join / Prune 5545 message, but the router has more than N (S,G,rpt) Prunes to add, then 5546 the router MUST choose to include the first N (numerically smallest in 5547 network byte order) IP addresses. 5549 4.9.6. Assert Message Format 5551 The Assert message is used to resolve forwarder conflicts between 5552 routers on a link. It is sent when a multicast data packet is received 5553 on an interface that the router would normally forward that packet. 5554 Assert messages may also be sent in response to an Assert message from 5555 another router. 5557 0 1 2 3 5558 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 5559 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5560 |PIM Ver| Type | Reserved | Checksum | 5561 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5562 | Group Address (Encoded-Group format) | 5563 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5564 | Source Address (Encoded-Unicast format) | 5565 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5566 |R| Metric Preference | 5567 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5568 | Metric | 5569 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5571 PIM Version, Type, Reserved, Checksum 5572 Described in Section 4.9. 5574 Group Address 5575 The group address for which the router wishes to resolve the 5576 forwarding conflict. This is an Encoded-Group address, as 5577 specified in Section 4.9.1. 5579 Source Address 5580 Source address for which the router wishes to resolve the 5581 forwarding conflict. The source address MAY be set to zero for 5582 (*,G) asserts (see below). The format for this address is given in 5583 Encoded-Unicast-Address in Section 4.9.1. 5585 R RPT-bit is a 1 bit value. The RPT-bit is set to 1 for Assert(*,G) 5586 messages and 0 for Assert(S,G) messages. 5588 Metric Preference 5589 Preference value assigned to the unicast routing protocol that 5590 provided the route to the multicast source or Rendezvous-Point. 5592 Metric 5593 The unicast routing table metric associated with the route used to 5594 reach the multicast source or Rendezvous-Point. The metric is in 5595 units applicable to the unicast routing protocol used. 5597 Assert messages can be sent to resolve a forwarding conflict for all 5598 traffic to given group or for a specific source and group. 5600 Assert(S,G) 5601 Source specific asserts are sent by routers forwarding a specific 5602 source on the shortest-path tree (SPTbit is TRUE). (S,G) Asserts 5603 have the Group-Address field set to the group G and the Source- 5604 Address field set to the source S. The RPT-bit is set to 0, the 5605 Metric-Preference is set to MRIB.pref(S) and the Metric is set to 5606 MRIB.metric(S). 5608 Assert(*,G) 5609 Group specific asserts are sent by routers forwarding data for the 5610 group and source(s) under contention on the shared tree. (*,G) 5611 asserts have the Group-Address field set to the group G. For data 5612 triggered Asserts the Source-Address field MAY be set to the IP 5613 source address of the data packet that triggered the Assert and is 5614 set to zero otherwise. The RPT-bit is set to 1, the Metric- 5615 Preference is set to MRIB.pref(RP(G)) and the Metric is set to 5616 MRIB.metric(RP(G)). 5618 4.10. PIM Timers 5620 PIM-SM maintains the following timers, as discussed in Section 4.1. All 5621 timers are countdown timers - they are set to a value and count down to 5622 zero, at which point they typically trigger an action. Of course they 5623 can just as easily be implemented as count-up timers, where the absolute 5624 expiry time is stored and compared against a real-time clock, but the 5625 language in this specification assumes that they count downwards to 5626 zero. 5628 Global Timers 5630 Per interface (I): 5632 Hello Timer: HT(I) 5634 Per neighbor (N): 5636 Neighbor Liveness Timer: NLT(N,I) 5638 Per active RP (RP): 5640 (*,*,RP) Join Expiry Timer: ET(*,*,RP,I) 5642 (*,*,RP) Prune-Pending Timer: PPT(*,*,RP,I) 5644 Per Group (G): 5646 (*,G) Join Expiry Timer: ET(*,G,I) 5648 (*,G) Prune-Pending Timer: PPT(*,G,I) 5650 (*,G) Assert Timer: AT(*,G,I) 5652 Per Source (S): 5654 (S,G) Join Expiry Timer: ET(S,G,I) 5656 (S,G) Prune-Pending Timer: PPT(S,G,I) 5658 (S,G) Assert Timer: AT(S,G,I) 5660 (S,G,rpt) Prune Expiry Timer: ET(S,G,rpt,I) 5662 (S,G,rpt) Prune-Pending Timer: PPT(S,G,rpt,I) 5664 Per active RP (RP): 5666 (*,*,RP) Upstream Join Timer: JT(*,*,RP) 5668 Per Group (G): 5670 (*,G) Upstream Join Timer: JT(*,G) 5672 Per Source (S): 5674 (S,G) Upstream Join Timer: JT(S,G) 5676 (S,G) Keepalive Timer: KAT(S,G) 5678 (S,G,rpt) Upstream Override Timer: OT(S,G,rpt) 5680 At the DRs or relevant Assert Winners only: 5682 Per Source,Group pair (S,G): 5684 Register-Stop Timer: RST(S,G) 5686 4.11. Timer Values 5688 When timers are started or restarted, they are set to default values. 5689 This section summarizes those default values. 5691 Note that protocol events or configuration may change the default value 5692 of a timer on a specific interface. When timers are initialized in this 5693 document the value specific to the interface in context must be used. 5695 Some of the timers listed below (Prune-Pending, Upstream Join, Upstream 5696 Override) can be set to values which depend on the settings of the 5697 Propagation_Delay and Override_Interval of the corresponding interface. 5698 The default values for these are given below. 5700 Variable Name: Propagation_Delay(I) 5702 r+-------------------------------+---------------+-----------------------+ 5703 | Value Name | Value | Explanation | 5704 | 5705 +-------------------------------+---------------+-----------------------+ 5706 | Propagation_delay_default | 0.5 secs | Expected | 5707 | | | propagation delay | 5708 | | | over the local | 5709 | | | link. | 5710 | 5711 +-------------------------------+---------------+-----------------------+ 5713 The default value of the Propagation_delay_default is chosen to be 5714 relatively large to provide compatibility with older PIM 5715 implementations. 5717 Variable Name: Override_Interval(I) 5719 r+--------------------------+-----------------+--------------------------+ 5720 | Value Name | Value | Explanation | 5721 | 5722 +--------------------------+-----------------+--------------------------+ 5723 | t_override_default | 2.5 secs | Default delay | 5724 | | | interval over | 5725 | | | which to randomize | 5726 | | | when scheduling a | 5727 | | | delayed Join | 5728 | | | message. | 5729 | 5730 +--------------------------+-----------------+--------------------------+ 5732 Timer Name: Hello Timer (HT(I)) 5734 m+----------------------+---------+---------------------------------------+ 5735 |Value Name | Value | Explanation | 5736 | 5737 +----------------------+---------+---------------------------------------+ 5738 |Hello_Period | 30 secs | Periodic interval for Hello messages. | 5739 | 5740 +----------------------+---------+---------------------------------------+ 5741 |Triggered_Hello_Delay | 5 secs | Randomized interval for initial Hello | 5742 | | | message on bootup or triggered Hello | 5743 | | | message to a rebooting neighbor. | 5744 | 5745 +----------------------+---------+---------------------------------------+ 5746 At system power-up, the timer is initialized to rand(0, 5747 Triggered_Hello_Delay) to prevent synchronization. When a new or 5748 rebooting neighbor is detected, a responding Hello is sent within 5749 rand(0, Triggered_Hello_Delay). 5751 Timer Name: Neighbor Liveness Timer (NLT(N,I)) 5753 m+--------------------------+-----------------------+--------------------+ 5754 | Value Name | Value | Explanation | 5755 | 5756 +--------------------------+-----------------------+--------------------+ 5757 | Default_Hello_Holdtime | 3.5 * Hello_Period | Default holdtime | 5758 | | | to keep neighbor | 5759 | | | state alive | 5760 | 5761 +--------------------------+-----------------------+--------------------+ 5762 | Hello_Holdtime | from message | Holdtime from | 5763 | | | Hello Message | 5764 | | | Holdtime option. | 5765 | 5766 +--------------------------+-----------------------+--------------------+ 5768 The Holdtime in a Hello Message should be set to (3.5 * Hello_Period), 5769 giving a default value of 105 seconds. 5771 Timer Names: Expiry Timer (ET(*,*,RP,I), ET(*,G,I), ET(S,G,I), 5772 ET(S,G,rpt,I)) 5774 (+----------------+-----------------+------------------------------------+ 5775 | Value Name | Value | Explanation | 5776 | 5777 +----------------+-----------------+------------------------------------+ 5778 | J/P_HoldTime | from message | Holdtime from Join/Prune Message | 5779 | 5780 +----------------+-----------------+------------------------------------+ 5782 See details of JT(*,G) for the Holdtime that is included in Join/Prune 5783 Messages. 5785 Timer Names: Prune-Pending Timer (PPT(*,*,RP,I), PPT(*,G,I), PPT(S,G,I), 5786 PPT(S,G,rpt,I)) 5788 T+---------------------------+---------------------+---------------------+ 5789 |Value Name | Value | Explanation | 5790 | 5791 +---------------------------+---------------------+---------------------+ 5792 |J/P_Override_Interval(I) | Default: | Short period after | 5793 | | Effective_ | a join or prune to | 5794 | | Propagation_ | allow other | 5795 | | Delay(I) + | routers on the LAN | 5796 | | EffectiveOverride_ | to override the | 5797 | | Interval(I) | join or prune | 5798 | 5799 +---------------------------+---------------------+---------------------+ 5801 Note that both the Effective_Propagation_Delay(I) and the 5802 Effective_Override_Interval(I) are interface specific values that may 5803 change when Hello messages are received (see section 4.3.3). 5805 Timer Names: Assert Timer (AT(*,G,I), AT(S,G,I)) 5807 m+---------------------------+----------------------+--------------------+ 5808 | Value Name | Value | Explanation | 5809 | 5810 +---------------------------+----------------------+--------------------+ 5811 | Assert_Override_Interval | Default: 3 secs | Short interval | 5812 | | | before an assert | 5813 | | | times out where | 5814 | | | the assert winner | 5815 | | | resends an Assert | 5816 | | | message | 5817 | 5818 +---------------------------+----------------------+--------------------+ 5819 | Assert_Time | Default: 180 secs | Period after last | 5820 | | | assert before | 5821 | | | assert state is | 5822 | | | timed out | 5823 | 5824 +---------------------------+----------------------+--------------------+ 5826 Note that for historical reasons, the Assert message lacks a Holdtime 5827 field. Thus changing the Assert Time from the default value is not 5828 recommended. 5830 Timer Names: Upstream Join Timer (JT(*,*,RP), JT(*,G), JT(S,G)) 5832 m+-------------+--------------------+-------------------------------------+ 5833 |Value Name | Value | Explanation | 5834 | 5835 +-------------+--------------------+-------------------------------------+ 5836 |t_periodic | Default: 60 secs | Period between Join/Prune Messages | 5837 | 5838 +-------------+--------------------+-------------------------------------+ 5839 |t_suppressed | rand(1.1 * | Suppression period when someone | 5840 | | t_periodic, 1.4 * | else sends a J/P message so we | 5841 | | t_periodic) when | don't need to do so. | 5842 | | Suppression_ | | 5843 | | Enabled(I) is | | 5844 | | true, 0 otherwise | | 5845 | 5846 +-------------+--------------------+-------------------------------------+ 5847 |t_override | rand(0, Effective_ | Randomized delay to prevent | 5848 | | Override_ | response implosion when sending a | 5849 | | Interval(I)) | join message to override someone | 5850 | | | else's Prune message. | 5851 | 5852 +-------------+--------------------+-------------------------------------+ 5854 t_periodic may be set to take into account such things as the configured 5855 bandwidth and expected average number of multicast route entries for the 5856 attached network or link (e.g., the period would be longer for lower- 5857 speed links, or for routers in the center of the network that expect to 5858 have a larger number of entries). If the Join/Prune-Period is modified 5859 during operation, these changes should be made relatively infrequently 5860 and the router should continue to refresh at its previous Join/Prune- 5861 Period for at least Join/Prune-Holdtime, in order to allow the upstream 5862 router to adapt. 5864 The holdtime specified in a Join/Prune message should be set to (3.5 * 5865 t_periodic). 5867 t_override depends on the Effective_Override_Interval of the upstream 5868 interface which may change when Hello messages are received. 5870 t_suppressed depends on the Suppression State of the upstream interface 5871 (Section 4.3.3) and becomes zero when suppression is disabled. 5873 Timer Name: Upstream Override Timer (OT(S,G,rpt)) 5875 m+---------------+---------------------------+---------------------------+ 5876 | Value Name | Value | Explanation | 5877 | 5878 +---------------+---------------------------+---------------------------+ 5879 | t_override | see Upstream Join Timer | see Upstream Join Timer | 5880 | 5881 +---------------+---------------------------+---------------------------+ 5883 The upstream Override Timer is only ever set to t_override; this value 5884 is defined in the section on Upstream Join Timers. 5886 Timer Name: Keepalive Timer (KAT(S,G)) 5888 m+-----------------------+------------------------+----------------------+ 5889 | Value Name | Value | Explanation | 5890 | 5891 +-----------------------+------------------------+----------------------+ 5892 | Keepalive_Period | Default: 210 secs | Period after last | 5893 | | | (S,G) data packet | 5894 | | | during which (S,G) | 5895 | | | Join state will be | 5896 | | | maintained even in | 5897 | | | the absence of | 5898 | | | (S,G) Join | 5899 | | | messages. | 5900 | 5901 +-----------------------+------------------------+----------------------+ 5902 | RP_Keepalive_Period | ( 3 * Register_ | As | 5903 | | Suppression_Time ) | Keepalive_Period, | 5904 | | + Register_ | but at the RP when | 5905 | | Probe_Time | a Register-Stop is | 5906 | | | sent. | 5907 | 5908 +-----------------------+------------------------+----------------------+ 5909 The normal keepalive period for the KAT(S,G) defaults to 210 seconds. 5910 However at the RP, the keepalive period must be at least the 5911 Register_Suppression_Time or the RP may time out the (S,G) state before 5912 the next Null-Register arrives. Thus the KAT(S,G) is set to 5913 max(Keepalive_Period, RP_Keepalive_Period) when a Register-Stop is sent. 5915 Timer Name: Register-Stop Timer (RST(S,G)) 5917 m+----------------------------+--------------------+---------------------+ 5918 |Value Name | Value | Explanation | 5919 | 5920 +----------------------------+--------------------+---------------------+ 5921 |Register_Suppression_Time | Default: 60 secs | Period during | 5922 | | | which a DR stops | 5923 | | | sending Register- | 5924 | | | encapsulated data | 5925 | | | to the RP after | 5926 | | | receiving a | 5927 | | | Register-Stop | 5928 | | | message. | 5929 | 5930 +----------------------------+--------------------+---------------------+ 5931 |Register_Probe_Time | Default: 5 secs | Time before RST | 5932 | | | expires when a DR | 5933 | | | may send a Null- | 5934 | | | Register to the RP | 5935 | | | to cause it to | 5936 | | | resend a Register- | 5937 | | | Stop message. | 5938 | 5939 +----------------------------+--------------------+---------------------+ 5940 If the the Register_Suppression_Time or the Register_Probe_Time are 5941 configured to values other than the defaults it MUST be ensured that the 5942 value of the Register_Probe_Time is less than half the value of the 5943 Register_Suppression_Time to prevent a possible negative value in the 5944 setting of the Register-Stop Timer. 5946 5. IANA Considerations 5948 5.1. PIM Address Family 5950 The PIM Address Family field was chosen to be 8 bits as a tradeoff 5951 between packet format and use of the IANA assigned numbers. Since when 5952 the PIM packet format was designed only 15 values were assigned for 5953 Address Families, and large numbers of new Address Family values were 5954 not envisioned, 8 bits seemed large enough. However, the IANA assigns 5955 Address Families in a 16-bit field. Therefore, the PIM Address Family 5956 is allocated as follows: 5958 Values 0 through 127 are designated to have the same meaning as 5959 IANA-assigned Address Family Numbers [6]. 5961 Values 128 through 250 are designated to be assigned for PIM by the 5962 IANA based upon IESG Approval, as defined in [8]. 5964 Values 251 through 255 are designated for Private Use, as defined 5965 in [8]. 5967 5.2. PIM Hello Options 5969 Values 17 through 65000 are to be assigned by the IANA. Since the space 5970 is large, they may be assigned as First Come First Served as defined in 5971 [8]. Such assignments are valid for one year, and may be renewed. 5972 Permanent assignments require a specification (see "Specification 5973 Required" in [8].) 5975 6. Security Considerations 5977 The IPsec authentication header [7] MAY be used to provide data 5978 integrity protection and groupwise data origin authentication of PIM 5979 protocol messages. Authentication of PIM messages can protect against 5980 unwanted behaviors caused by unauthorized or altered PIM messages. 5982 6.1. Attacks based on forged messages 5984 The extent of possible damage depends on the type of counterfeit 5985 messages accepted. We next consider the impact of possible forgeries, 5986 including forged link-local (Join/Prune, Hello, and Assert) and forged 5987 unicast (Register and Register-Stop) messages. 5989 6.1.1. Forged link-local messages 5991 Join/Prune, Hello, and Assert messages are all sent to the link-local 5992 ALL_PIM_ROUTERS multicast addresses, and thus are not forwarded by a 5993 compliant router. A forged message of this type can only reach a LAN if 5994 it was sent by a local host or if it was allowed onto the LAN by a 5995 compromised or non-compliant router. 5997 1. A forged Join/Prune message can cause multicast traffic to be 5998 delivered to links where there are no legitimate requesters, 5999 potentially wasting bandwidth on that link. A forged leave message 6000 on a multi-access LAN is generally not a significant attack in PIM, 6001 because any legitimately joined router on the LAN would override 6002 the leave with a join before the upstream router stops forwarding 6003 data to the LAN. 6005 2. By forging a Hello message, an unauthorized router can cause 6006 itself to be elected as the designated router on a LAN. The 6007 designated router on a LAN is (in the absence of asserts) 6008 responsible for forwarding traffic to that LAN on behalf of any 6009 local members. The designated router is also responsible for 6010 register-encapsulating to the RP any packets that are originated by 6011 hosts on the LAN. Thus, the ability of local hosts to send and 6012 receive multicast traffic may be compromised by a forged Hello 6013 message. 6015 3. By forging an Assert message on a multi-access LAN, an attacker 6016 could cause the legitimate designated forwarder to stop forwarding 6017 traffic to the LAN. Such a forgery would prevent any hosts 6018 downstream of that LAN from receiving traffic. 6020 6.1.2. Forged unicast messages 6022 Register messages and Register-Stop messages are forwarded by 6023 intermediate routers to their destination using normal IP forwarding. 6024 Without data origin authentication, an attacker who is located anywhere 6025 in the network may be able to forge a Register or Register-Stop message. 6026 We consider the effect of a forgery of each of these messages next. 6028 1 By forging a Register message, an attacker can cause the RP to 6029 inject forged traffic onto the shared multicast tree. 6031 2 By forging a Register-stop message, an attacker can prevent a 6032 legitimate DR from Registering packets to the RP. This can prevent 6033 local hosts on that LAN from sending multicast packets. 6035 The above two PIM messages are not changed by intermediate routers and 6036 need only be examined by the intended receiver. Thus these messages can 6037 be authenticated end-to-end, using AH. Attacks on Register and 6038 Register-Stop messages do not apply to a PIM-SSM-only implementation, as 6039 these messages are not required for PIM-SSM. 6041 6.2. Non-cryptographic Authentication Mechanisms 6043 A PIM router SHOULD provide an option to limit the set of neighbors from 6044 which it will accept Join/Prune, Assert, and Hello messages. Either 6045 static configuration of IP addresses or an IPsec security association 6046 may be used. Furthermore, a PIM router SHOULD NOT accept protocol 6047 messages from a router from which it has not yet received a valid Hello 6048 message. 6050 A Designated Router MUST NOT register-encapsulate a packet and send it 6051 to the RP unless the source address of the packet is a legal address for 6052 the subnet on which the packet was received. Similarly, a Designated 6053 Router SHOULD NOT accept a Register-Stop packet whose IP source address 6054 is not a valid RP address for the local domain. 6056 An implementation SHOULD provide a mechanism to allow an RP to restrict 6057 the range of source addresses from which it accepts Register- 6058 encapsulated packets. 6060 All options that restrict the range of addresses from which packets are 6061 accepted MUST default to allowing all packets. 6063 6.3. Authentication using IPsec 6065 The IPsec [7] transport mode using the Authentication Header (AH) is the 6066 recommended method to prevent the above attacks against PIM. The 6067 specific AH authentication algorithm and parameters, including the 6068 choice of authentication algorithm and the choice of key, are configured 6069 by the network administrator. When IPsec authentication is used, a PIM 6070 router should reject (drop without processing) any unauthorized PIM 6071 protocol messages. 6073 As of this writing, the IPsec anti-replay option does not handle the 6074 case of a Security Association identified by a multicast destination 6075 address. Thus, the anti-replay option currently must be disabled on 6076 these Security Associations. Until replay prevention for link-local 6077 multicast messages is addressed (one such proposal is [14]), the anti- 6078 replay option SHOULD be enabled on all security associations having a 6079 unicast destination address. 6081 To use IPsec, the administrator of a PIM network configures each PIM 6082 router with one or more Security Associations and associated SPI(s) that | 6083 are used by senders to authenticate PIM protocol messages and are used 6084 by receivers to authenticate received PIM protocol messages. This 6085 document does not describe protocols for establishing Security 6086 Associations. It assumes that manual configuration of Security 6087 Associations is performed, but it does not preclude the use of a 6088 negotiation protocol such as The Internet Key Exchange [13] to establish 6089 Security Associations. 6091 The following sections describe the Security Associations required to 6092 protect PIM protocol messages. 6094 6.3.1. Protecting link-local multicast messages 6096 The network administrator defines a Security Association (SA) and 6097 Security Parameters Index (SPI) that is to be used to authenticate all 6098 link-local PIM protocol messages (Hello, Join/Prune, and Assert) on each 6099 link in a PIM domain. All link-local PIM protocol messages use SPI 0. 6101 The Security Policy Database at a PIM router should be configured to 6102 ensure that all incoming and outgoing Join/Prune, Assert, and Hello 6103 packets use the SA associated with the interface to which the packet is 6104 sent. 6106 Note that, according to [7] there is nominally a different Security 6107 Association Database (SAD) for each router interface. Thus, the 6108 selected Security Association for an inbound PIM packet can vary 6109 depending on the interface on which the packet arrived. This fact 6110 allows the network administrator to use different authentication methods 6111 for each link, even though the destination address is the same for all 6112 link-local PIM packets, regardless of interface. 6114 6.3.2. Protecting unicast messages 6116 IPSec can also be used to provide data origin authentication and data 6117 integrity protection for the Register and Register-Stop unicast 6118 messages. 6120 6.3.2.1. Register messages 6122 The Security Policy Database at every PIM router is configured to select 6123 a Security Association to use when sending PIM Register packets to each 6124 rendezvous point. 6126 In the most general mode of operation, the Security Policy Database at 6127 each DR is configured to select a unique SA and SPI for traffic sent to 6128 each RP. This allows each DR to have a different authentication 6129 algorithm and key to talk to the RP. However, this creates a daunting 6130 key management and distribution problem for the network administrator. 6131 Therefore, it may be preferable in PIM domains where all Designated 6132 Routers are under a single administrative control, to use the same 6133 authentication algorithm parameters (including the key) for all 6134 Registered packets in a domain, regardless of who is the RP and 6135 regardless of who is the DR. 6137 In this "single shared key" mode of operation, the network administrator 6138 must choose an SPI for each DR that will be used to send it PIM protocol 6139 packets. The Security Policy Database at every DR is configured to 6140 select a Security Association (including the authentication algorithm, 6141 authentication parameters, and this SPI) when sending Register messages 6142 to this RP. 6144 By using a single authentication algorithm and associated parameters, 6145 the key distribution problem is simplified. Note however, that this 6146 method has the property that, in order to change the authentication 6147 method or authentication key used, all routers in the domain must be 6148 updated. 6150 6.3.2.2. Register-Stop messages 6152 Similarly, the Security Policy Database at each Rendezvous Point should 6153 be configured to choose a Security Association to use when sending 6154 Register-Stop messages. Because Register-Stop messages are unicast to 6155 the destination DR, a different Security Association and a potentially 6156 unique SPI is required for each DR. 6158 In order to simplify the management problem, it may be acceptable to use 6159 the same authentication algorithm and authentication parameters, 6160 regardless of the sending RP and regardless of the destination DR. 6161 Although a unique Security Association is needed for each DR, the same 6162 authentication algorithm and authentication algorithm parameters (secret 6163 key) can be shared by all DRs and by all RPs. 6165 6.4. Denial of Service Attacks 6167 There are a number of possible denial of service attacks against PIM 6168 that can be caused by generating false PIM protocol messages or even by 6169 generating data false traffic. Authenticating PIM protocol traffic 6170 prevents some, but not all of these attacks. Two of the possible 6171 attacks include: 6173 - Sending packets to many different group addresses quickly can be a 6174 denial of service attack in and of itself. This will cause many 6175 register-encapsulated packets, loading the DR, the RP, and the 6176 routers between the DR and the RP. 6178 - Forging Join messages can cause a multicast tree to get set up. A 6179 large number of forged joins can consume router resources and 6180 result in denial of service. 6182 7. Authors' Addresses 6184 Bill Fenner 6185 AT&T Labs - Research 6186 75 Willow Road 6187 Menlo Park, CA 94025 6188 fenner@research.att.com 6190 Mark Handley 6191 Department of Computer Science 6192 University College London 6193 Gower Street 6194 London WC1E 6BT 6195 United Kingdom 6196 M.Handley@cs.ucl.ac.uk 6197 Hugh Holbrook 6198 Cisco Systems 6199 170 W. Tasman Drive 6200 San Jose, CA 95134 6201 holbrook@cisco.com 6203 Isidor Kouvelas 6204 Cisco Systems 6205 170 W. Tasman Drive 6206 San Jose, CA 95134 6207 kouvelas@cisco.com 6209 8. Acknowledgments 6211 PIM-SM was designed over many years by a large group of people, 6212 including ideas, comments, and corrections from Deborah Estrin, Dino 6213 Farinacci, Ahmed Helmy, David Thaler, Steve Deering, Van Jacobson, C. 6214 Liu, Puneet Sharma, Liming Wei, Tom Pusateri, Tony Ballardie, Scott 6215 Brim, Jon Crowcroft, Paul Francis, Joel Halpern, Horst Hodel, Polly 6216 Huang, Stephen Ostrowski, Lixia Zhang, Girish Chandranmenon, Brian 6217 Haberman, Hal Sandick, Mike Mroz, Garry Kump, Pavlin Radoslavov, Mike 6218 Davison, James Huang, Christopher Thomas Brown, and James Lingard. 6220 Thanks are due to the American Licorice Company, for its obscure but 6221 possibly essential role in the creation of this document. 6223 9. Normative References 6225 [1] B. Cain, S. Deering, I. Kouvelas, B. Fenner, A. Thyagarajan, 6226 "Internet Group Management Protocol, Version 3", RFC 3376. 6228 [2] S.E. Deering, "Host extensions for IP multicasting", RFC 1112, Aug 6229 1989. 6231 [3] S. Deering, W. Fenner, B. Haberman, "Multicast Listener Discovery 6232 (MLD) for IPv6", RFC 2710. 6234 [4] S. Deering, R. Hinden, "Internet Protocol, Version 6 (IPv6) 6235 Specification", RFC 2460. 6237 [5] H. Holbrook, B. Cain, "Source-Specific Multicast for IP", draft- 6238 ietf-ssm-arch-04.txt, work in progress. 6240 [6] IANA, "Address Family Numbers", linked from 6241 http://www.iana.org/numbers.html 6243 [7] S. Kent, R. Atkinson, "Security Architecture for the Internet 6244 Protocol.", RFC 2401. 6246 [8] T. Narten , H. Alvestrand, "Guidelines for Writing an IANA 6247 Considerations Section in RFCs", RFC 2434. 6249 10. Informative References 6251 [9] T. Bates , R. Chandra , D. Katz , Y. Rekhter, "Multiprotocol 6252 Extensions for BGP-4", RFC 2283 6254 [10] D. Black, "Differentiated Services and Tunnels", RFC 2983. 6256 [11] W. Fenner, M. Handley, R. Kermode, D. Thaler, "Bootstrap Router 6257 (BSR) Mechanism for PIM Sparse Mode", draft-ietf-pim-sm-bsr-03.txt, 6258 work in progress. 6260 [12] M. Handley, I. Kouvelas, T. Speakman, L. Vicisano, "Bi-directional 6261 Protocol Independent Multicast", draft-ietf-pim-bidir-05.txt, work 6262 in progress. 6264 [13] D. Harkins, D. Carrell, "The Internet Key Exchange (IKE)", RFC 6265 2409. 6267 [14] S. Kent, "IP Encapsulating Security Payload (ESP)", draft-ietf- 6268 ipsec-esp-v3-06.txt, work in progress. 6270 [15] P. Savola, B. Haberman, "Embedding the Rendezvous Point (RP) 6271 Address in an IPv6 Multicast Address" draft-ietf-mboned- 6272 embeddedrp-04.txt, work in progress. 6274 [16] D. Thaler, "Interoperability Rules for Multicast Routing 6275 Protocols", RFC 2715. 6277 11. Appendix A: PIM Multicast Border Router Behavior 6279 In some cases PIM-SM domains will interconnect with non-PIM multicast 6280 domains. In these cases, the border routers of the PIM domain speak 6281 PIM-SM on some interfaces and speak other multicast routing protocols on 6282 other interfaces. Such routers are termed PIM Multicast Border Routers 6283 or PMBRs. In general, RFC 2715 [16] provides rules for interoperability 6284 between different multicast routing protocols. In this section we 6285 specify how PMBRs differ from regular PIM-SM routers. 6287 From the point of view of PIM-SM, a PMBR has two tasks: 6289 o To ensure that traffic from sources outside the PIM-SM domain reaches 6290 receivers inside the domain. 6292 o To ensure that traffic from sources inside the PIM-SM domain reaches 6293 receivers outside the domain. 6295 We note that multiple PIM-SM domains are sometimes connected together 6296 using protocols such as MSDP, which provides information about active 6297 external sources, but does not follow RFC 2715. In such cases the 6298 domains are not connected via PMBRs because Join(S,G) messages traverse 6299 the border between domains. A PMBR is required when no PIM messages can 6300 traverse the border. 6302 11.1. Sources External to the PIM-SM Domain 6304 A PMBR needs to ensure that traffic from multicast sources external to 6305 the PIM-SM domain reaches receivers inside the domain. The PMBR will 6306 follow the rules in RFC 2715, such that traffic from external sources 6307 reaches the PMBR itself. 6309 According to RFC 2715, the PIM-SM component of the PMBR will receive an 6310 (S,G) Creation event when data from an (S,G) data packet from an 6311 external source first reaches the PMBR. If RPF_interface(S) is an 6312 interface in the PIM-SM domain, the packet cannot be originated into the 6313 PIM domain at this router, and the PIM-SM component of the PMBR will not 6314 process the packet. Otherwise the PMBR will then act exactly as if it 6315 were the DR for this source (see Section 4.4.1), with the following 6316 modifications: 6318 o The Border-bit is set in all PIM Register message sent for these 6319 sources. 6321 o DirectlyConnected(S) is treated as being TRUE for these sources. 6323 o The PIM-SM forwarding rule "iif == RPF_interface(S)" is relaxed to be 6324 TRUE if iif is any interface that is not part of the PIM-SM component 6325 of the PMBR (see Section 4.2). 6327 11.2. Sources Internal to the PIM-SM Domain 6329 A PMBR needs to ensure that traffic from sources inside the PIM-SM 6330 domain reaches receivers outside the domain. Using terminology from RFC 6331 2715, there are two possible scenarios for this: 6333 o Another component of the PMBR is a wildcard receiver. In this case 6334 the PIM-SM component of the PMBR must ensure that traffic from all 6335 internal sources reaches the PMBR until it is informed otherwise. 6337 Note that certain profiles of PIM-SM, e.g., PIM-SSM, PIM-SM with 6338 Embedded RP, cannot interoperate with a neighboring wildcard receiver 6339 domain. 6341 o No other component of the PMBR is a wildcard receiver. In this case 6342 the PMBR will receive explicit information as to which groups or 6343 (source,group) pairs the external domains wish to receive. 6345 In the former case, the PMBR will need to send a Join(*,*,RP) to all the 6346 active RPs in the PIM-SM domain. It may also send a Join(*,*,RP) to all 6347 the candidate RPs in the PIM-SM domain. This will cause all traffic in 6348 the domain to reach the PMBR. The PMBR may then act as if it were a DR 6349 with directly connected receivers, and trigger the transition to a 6350 shortest path tree (see Section 4.2.1). 6352 In the latter case, the PMBR will not need to send Join(*,*,RP) 6353 messages. However the PMBR will still need to act as a DR with directly 6354 connected receivers on behalf of the external receivers in terms of 6355 being able to switch to the shortest-path tree for internally-reached 6356 sources. 6358 According to RFC 2715, the PIM-SM component of the PMBR may receive a 6359 number of alerts generated by events in the external routing components. 6360 To implement the above behavior, one reasonable way to map these alerts 6361 into PIM-SM state as follows: 6363 o When a PIM-SM component receives an (S,G) Prune alert, it sets 6364 local_receiver_include(S,G,I) to FALSE for the discard interface. 6366 o When a PIM-SM component receives a (*,G) Prune alert, it sets 6367 local_receiver_include(*,G,I) to FALSE for the discard interface. 6369 o When a PIM-SM component receives an (S,G) Join alert, it sets 6370 local_receiver_include(S,G,I) to TRUE for the discard interface. 6372 o When a PIM-SM component receives a (*,G) Join alert, it sets 6373 local_receiver_include(*,G,I) to TRUE for the discard interface. 6375 o When a PIM-SM component receives a (*,*) Join alert, it sets 6376 DownstreamJPState(*,*,RP,I) to Join state on the discard interface for 6377 all RPs in the PIM-SM domain. 6379 o When a PIM-SM component receives a (*,*) Prune alert, then it sets 6380 DownstreamJPState(*,*,RP,I) to NoInfo state on the discard interface 6381 for all RPs in the PIM-SM domain. 6383 We refer above to the discard interface because the macros and state 6384 machines are interface-specific, but we need to have PIM state that is 6385 not associated with any actual PIM-SM interface. Implementors are free 6386 to implement this in any reasonable manner. 6388 Note that these state changes will then cause additional PIM-SM state 6389 machine transitions in the normal way. 6391 These rules are however not sufficient to allow pruning off the (*,*,RP) 6392 tree. Some additional rules provide guidance as to one way this may be 6393 done: 6395 o If the PMBR has joined on the (*,*,RP) tree, then it should set 6396 DownstreamJPState(*,G,I) to JOIN on the discard interface for all 6397 active groups. 6399 o If the router receives a (S,G) prune alert it will need to set 6400 DownstreamJPState(S,G,rpt,I) to PRUNE on the discard interface. 6402 o If the router receives a (*,G) prune alert, it will need to set 6403 DownstreamJPState(S,G,rpt,I) to PRUNE on the discard interface for all 6404 active sources sending to G. 6406 The rationale for this is that there is no way in PIM-SM to prune 6407 traffic off the (*,*,RP) tree, except by Joining the (*,G) tree and then 6408 pruning each source individually. 6410 12. Index 6411 Assert(*,G). . . . . . . . . . . . . . . . . . . . . . . . . . . .27,127 6412 Assert(S,G). . . . . . . . . . . . . . . . . . . . . . . . . . . .27,127 6413 AssertCancel(*,G). . . . . . . . . . . . . . . . . . . . . . . . . 97,99 6414 AssertCancel(S,G). . . . . . . . . . . . . . . . . . . . . . . .79,90,99 6415 AssertTimer(*,G,I) . . . . . . . . . . . . . . . . . . . . .16,25,91,131 6416 AssertTimer(S,G,I) . . . . . . . . . . . . . . . . . . . . .18,25,83,131 6417 AssertTrackingDesired(*,G,I) . . . . . . . . . . . . . . . . . .93,94,96 6418 AssertTrackingDesired(S,G,I) . . . . . . . . . . . . . . . . 85,85,87,89 6419 AssertWinner(*,G,I). . . . . . . . . . . . . . . . . .17,22,25,93,97,100 6420 AssertWinner(S,G,I). . . . . . . . . . . . . . . . 18,23,25,85,89,99,100 6421 AssertWinnerMetric(*,G,I). . . . . . . . . . . . . . . . . . . 17,97,100 6422 AssertWinnerMetric(S,G,I). . . . . . . . . . . . . . . . . . . 18,89,100 6423 assert_metric. . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 6424 Assert_Override_Interval . . . . . . . . . . . . . . . . . . . 89,96,131 6425 Assert_Time. . . . . . . . . . . . . . . . . . . . . . . . . . 89,96,131 6426 AT(*,G,I). . . . . . . . . . . . . . . . . . . . . . . .16,25,91,128,131 6427 AT(S,G,I). . . . . . . . . . . . . . . . . . . . . . . .18,25,83,128,131 6428 CheckSwitchToSpt(S,G). . . . . . . . . . . . . . . . . . . . . . . 27,28 6429 CouldAssert(*,G,I) . . . . . . . . . . . . . . . . . . . .91,93,94,95,98 6430 CouldAssert(S,G,I) . . . . . . . . . . . . . . . . . . 83,85,87,88,89,98 6431 CouldRegister(S,G) . . . . . . . . . . . . . . . . . . . . . . . . 38,40 6432 Default_Hello_Holdtime . . . . . . . . . . . . . . . . . . . . . . . 33 6433 DirectlyConnected(S) . . . . . . . . . . . . . . . . . . 27,27,29,40,142 6434 DownstreamJPState(*,*,RP,I). . . . . . . . . . . . . . . . . . . .23,144 6435 DownstreamJPState(*,G,I) . . . . . . . . . . . . . . . . . . . . . . 23 6436 DownstreamJPState(S,G,I) . . . . . . . . . . . . . . . . . . . . . 24,40 6437 DownstreamJPState(S,G,rpt,I) . . . . . . . . . . . . . . . . . . . . 24 6438 DR(I). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 6439 dr_is_better(a,b,I). . . . . . . . . . . . . . . . . . . . . . . . 33,33 6440 DR_Priority. . . . . . . . . . . . . . . . . . . . . . . . . . .31,32,33 6441 Effective_Override_Interval(I) . . . . . . . . . . . . . . . .36,113,131 6442 Effective_Propagation_Delay(I) . . . . . . . . . . . . . . . . . .35,131 6443 ET(*,*,RP,I) . . . . . . . . . . . . . . . . . . . . . . . 15,46,127,130 6444 ET(*,G,I). . . . . . . . . . . . . . . . . . . . . . . . . 16,49,128,130 6445 ET(S,G,I). . . . . . . . . . . . . . . . . . . . . . . . . 18,53,128,130 6446 ET(S,G,rpt,I). . . . . . . . . . . . . . . . . . . . . .21,56,58,128,130 6447 GenID. . . . . . . . . . . . . . . . . . . 16,18,20,31,63,67,70,72,83,91 6448 Hash_Function. . . . . . . . . . . . . . . . . . . . . . . . . . .13,105 6449 Hello_Holdtime . . . . . . . . . . . . . . . . . . . . . . . . . .33,130 6450 Hello_Period . . . . . . . . . . . . . . . . . . . . . . . . . . .31,129 6451 HT(I). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .31,129 6452 IGMP . . . . . . . . . . . . . . . . . . . . . . . . . 7,9,17,23,101,104 6453 immediate_olist(*,*,RP). . . . . . . . . . . . . . . . . . . . . . 22,63 6454 immediate_olist(*,G) . . . . . . . . . . . . . . . . . . . . . . . 22,68 6455 immediate_olist(S,G) . . . . . . . . . . . . . . . . . . . . . .22,40,72 6456 infinite_assert_metric() . . . . . . . . . . . . . . . . . . . . . . 98 6457 inherited_olist(S,G) . . . . . . . . . . . . . . . . .22,27,43,72,85,107 6458 inherited_olist(S,G,rpt) . . . . . . . . . . . . . . . 22,27,29,76,78,80 6459 Interface_Address_List . . . . . . . . . . . . . . . . . . . . . . . 31 6460 I_Am_Assert_Loser(*,G,I) . . . . . . . . . . . . . . . . . . . . . . 25 6461 I_Am_Assert_Loser(S,G,I) . . . . . . . . . . . . . . . . . . . . . . 25 6462 I_am_DR(I) . . . . . . . . . . . . . . . . . . . . . . . .22,33,40,85,93 6463 I_am_RP(G) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43,44 6464 J/P_Holdtime . . . . . . . . . . . . . .47,50,54,58,64,69,74,120,130,132 6465 J/P_Override_Interval(I) . . . . . . . . . . . . . . 47,51,54,58,120,131 6466 JoinDesired(*,*,RP). . . . . . . . . . . . . . . . . . . . . . . . 63,77 6467 JoinDesired(*,G) . . . . . . . . . . . . . . . . . . . . .17,68,77,85,97 6468 JoinDesired(S,G) . . . . . . . . . . . . . . . . . . . 19,29,72,85,88,90 6469 joins(*,*,RP(G)) . . . . . . . . . . . . . . . . . . . . . . . . . . 22 6470 joins(*,*,RP). . . . . . . . . . . . . . . . . . . . . . . . 22,23,85,93 6471 joins(*,G) . . . . . . . . . . . . . . . . . . . . . . . . . 22,23,85,93 6472 joins(S,G) . . . . . . . . . . . . . . . . . . . . . . . . . . .22,24,85 6473 JT(*,*,RP) . . . . . . . . . . . . . . . . . . . . . . . . 15,61,128,132 6474 JT(*,G). . . . . . . . . . . . . . . . . . . . . . . . . . 17,66,128,132 6475 JT(S,G). . . . . . . . . . . . . . . . . . . . . . . . . . 18,71,128,132 6476 KAT(S,G) . . . . . . . . . . . . . . . .19,26,27,28,40,43,72,107,128,133 6477 KeepaliveTimer(S,G). . . . . . . . . 19,26,27,27,28,40,43,72,107,128,133 6478 Keepalive_Period . . . . . . . . . . . . . . . . . . . . . . . . .27,133 6479 lan_delay_enabled(I) . . . . . . . . . . . . . . . . . . . . . . . 35,36 6480 LAN_Prune_Delay. . . . . . . . . . . . . . . . . . . . . . . . . . . 31 6481 local_receiver_exclude(S,G,I). . . . . . . . . . . . . . . . . . . . 23 6482 local_receiver_include(*,G,I). . . . . . . . . . . . . . . . . 23,93,143 6483 local_receiver_include(S,G,I). . . . . . . . . . . . . . . . . . . 23,85 6484 local_receiver_include(S,G,I). . . . . . . . . . . . . . . . . . . . 143 6485 lost_assert(*,G) . . . . . . . . . . . . . . . . . . . . . . . .22,24,85 6486 lost_assert(*,G,I) . . . . . . . . . . . . . . . . . . . . . . 22,24,100 6487 lost_assert(S,G) . . . . . . . . . . . . . . . . . . . . . . . . . 22,24 6488 lost_assert(S,G,I) . . . . . . . . . . . . . . . . . . . . . . .23,24,99 6489 lost_assert(S,G,rpt) . . . . . . . . . . . . . . . . . . . . . . . . 24 6490 lost_assert(S,G,rpt,I) . . . . . . . . . . . . . . . . . . . . . . 24,99 6491 MBGP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7,8 6492 MFIB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7,14 6493 MLD. . . . . . . . . . . . . . . . . . . . . . . . . . 7,9,17,23,101,104 6494 MRIB . . . . . . . . . . . . . . .7,8,12,16,20,25,61,65,65,75,98,102,127 6495 MRIB.next_hop(host). . . . . . . . . . . . . . . . . . . . . 25,25,61,63 6496 my_assert_metric(S,G,I). . . . . . . . . . . . . . . . . .85,89,91,93,98 6497 NBR(Interface,IP_address). . . . . . . . . . . . . . . . .26,37,61,63,65 6498 NLT(N,I) . . . . . . . . . . . . . . . . . . . . . . . . . 15,33,127,130 6499 OT(S,G,rpt). . . . . . . . . . . . . . . . . . . . . . . . 21,76,128,133 6500 Override_Interval(I) . . . . . . . . . . . . . . 14,31,34,36,113,129,131 6501 packet_arrives_on_rp_tunnel(pkt) . . . . . . . . . . . . . . . . . . 43 6502 pim_exclude(S,G) . . . . . . . . . . . . . . . . . . . . . . 22,23,28,85 6503 pim_include(*,G) . . . . . . . . . . . . . . . . . . . 17,22,22,28,85,93 6504 pim_include(S,G) . . . . . . . . . . . . . . . . . . . . .19,22,23,28,85 6505 PPT(*,*,RP,I). . . . . . . . . . . . . . . . . . . . . . . 15,46,127,131 6506 PPT(*,G,I) . . . . . . . . . . . . . . . . . . . . . . . . 16,49,128,131 6507 PPT(S,G,I) . . . . . . . . . . . . . . . . . . . . . . . . 18,53,128,131 6508 PPT(S,G,rpt,I) . . . . . . . . . . . . . . . . . . . . .21,56,58,128,131 6509 Propagation_Delay(I) . . . . . . . . . . . . . . . . . . . 31,35,129,131 6510 Propagation_delay_default. . . . . . . . . . . . . . . . . . . . .35,129 6511 PruneDesired(S,G,rpt). . . . . . . . . . . . . . . . . . . . 78,79,88,90 6512 prunes(S,G,rpt). . . . . . . . . . . . . . . . . . . . . . . . .22,24,85 6513 Register-Stop(*,G) . . . . . . . . . . . . . . . . . . . . . . . . . 41 6514 Register-Stop(S,G) . . . . . . . . . . . . . . . . . . . . . . . . . 43 6515 Register-StopTimer(S,G). . . . . . . . . . . . . . . . . . 38,39,128,133 6516 Register_Probe_Time. . . . . . . . . . . . . . . . . . . . . . 39,44,133 6517 Register_Suppression_Time. . . . . . . . . . . . . . . . . . . 39,44,133 6518 RP(G). . . . . . . . . . . . . . 6,22,25,40,43,49,68,76,85,93,98,101,127 6519 RPF. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 6520 RPF'(*,G). . . . . . . . . . . . . . . . . . 25,29,66,67,70,76,77,97,100 6521 RPF'(S,G). . . . . . . . . . . . . . . . . . . . . 25,29,71,76,77,90,100 6522 RPF'(S,G,rpt). . . . . . . . . . . . . . . . . . . . . . . .25,76,78,101 6523 RPF_interface. . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 6524 RPF_interface(host). . . . . . . . 25,27,29,40,68,69,74,85,93,99,107,142 6525 RPTJoinDesired(G). . . . . . . . . . . . . . . . . . . . . . . .77,80,93 6526 rpt_assert_metric(G,I) . . . . . . . . . . . . . . . . . . . . . . 96,98 6527 RST(S,G) . . . . . . . . . . . . . . . . . . . . . . . . . 38,39,128,133 6528 SPTbit(S,G). . . . . . . . . .20,27,29,43,52,73,76,78,85,85,89,90,99,107 6529 spt_assert_metric(S,I) . . . . . . . . . . . . . . . . . . . . .89,98,99 6530 SSM. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .11,105 6531 Suppression_Enabled(I) . . . . . . . . . . . . . . . . . . . . . .36,132 6532 SwitchToSptDesired(S,G). . . . . . . . . . . . . . . . . . . . .28,28,43 6533 TIB. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7,14,26 6534 Triggered_Hello_Delay. . . . . . . . . . . . . . . . . . . . . 31,32,129 6535 t_joinsuppress . . . . . . . . . . . . . . . . . . . . . .63,64,67,69,74 6536 t_override . . . . . . . . . . . . . . . . . . . . . 63,67,72,77,132,133 6537 t_override_default . . . . . . . . . . . . . . . . . . . . . . . .36,129 6538 t_periodic . . . . . . . . . . . . . . . . . . . . . . . . .63,67,72,132 6539 t_suppressed . . . . . . . . . . . . . . . . . . . . .37,64,69,72,74,132 6540 Update_SPTbit(S,G,iif) . . . . . . . . . . . . . . . . . . . . . . 27,29 6541 UpstreamJPState(S,G) . . . . . . . . . . . . . . . . . . . . . . .27,107 6542 The IETF takes no position regarding the validity or scope of any 6543 Intellectual Property Rights or other rights that might be claimed to 6544 pertain to the implementation or use of the technology described in this 6545 document or the extent to which any license under such rights might or 6546 might not be available; nor does it represent that it has made any 6547 independent effort to identify any such rights. Information on the 6548 procedures with respect to rights in RFC documents can be found in BCP 6549 78 and BCP 79. 6551 Copies of IPR disclosures made to the IETF Secretariat and any 6552 assurances of licenses to be made available, or the result of an attempt 6553 made to obtain a general license or permission for the use of such 6554 proprietary rights by implementers or users of this specification can be 6555 obtained from the IETF on-line IPR repository at 6556 http://www.ietf.org/ipr. 6558 The IETF invites any interested party to bring to its attention any 6559 copyrights, patents or patent applications, or other proprietary rights 6560 that may cover technology that may be required to implement this 6561 standard. Please address the information to the IETF at ietf- 6562 ipr@ietf.org. 6564 13. Full Copyright Statement 6566 Copyright (C) The Internet Society (2004). This document is subject to 6567 the rights, licenses and restrictions contained in BCP 78, and except as 6568 set forth therein, the authors retain all their rights. 6570 This document and the information contained herein are provided on an 6571 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR 6572 IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET 6573 ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, 6574 INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE 6575 INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 6576 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.