idnits 2.17.1 draft-ietf-pim-sm-v2-new-10.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 6570. -- Found old boilerplate from RFC 3979, Section 5, paragraph 1 on line 6543. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 6550. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 6556. ** 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 138 longer pages, the longest (page 128) being 79 lines == It seems as if not all pages are separated by form feeds - found 0 form feeds but 148 pages Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** There are 773 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 1308: '...Hello messages MUST be sent on all act...' RFC 2119 keyword, line 1314: '...liant PIM router MUST send Hello messa...' RFC 2119 keyword, line 1330: '...address, then it MUST immediately send...' RFC 2119 keyword, line 1336: '...ity. The DR_Priority Option SHOULD be...' RFC 2119 keyword, line 1343: '...r (GenID) Option SHOULD be included in...' (70 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 (18 July 2004) is 7222 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 4067 -- Looks like a reference, but probably isn't: 'Actions A6' on line 3709 -- Looks like a reference, but probably isn't: 'Actions A3' on line 4081 -- Looks like a reference, but probably isn't: 'Actions A2' on line 4097 -- Looks like a reference, but probably isn't: 'Actions A4' on line 4081 -- Looks like a reference, but probably isn't: 'Actions A5' on line 4111 ** 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 (~~), 12 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-10.txt Mark Handley/UCL 4 Hugh Holbrook/Cisco 5 Isidor Kouvelas/Cisco 6 18 July 2004 7 Expires: January 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 . . . . . . 28 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 . . . . . . . 36 70 4.4. PIM Register Messages. . . . . . . . . . . . . . . . 37 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 utilisation, 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) (+) immediate_olist(S,G) 939 The macros pim_include(*,G) and pim_include(S,G) indicate the interfaces 940 to which traffic might be forwarded because of hosts that are local 941 members on that interface. Note that normally only the DR cares about 942 local membership, but when an assert happens, the assert winner takes 943 over responsibility for forwarding traffic to local members that have 944 requested traffic on a group or source/group pair. 946 pim_include(*,G) = 947 { all interfaces I such that: 948 ( ( I_am_DR( I ) AND lost_assert(*,G,I) == FALSE ) 949 OR AssertWinner(*,G,I) == me ) 950 AND local_receiver_include(*,G,I) } 952 pim_include(S,G) = 953 { 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(S,G,I) == FALSE ) 962 OR AssertWinner(S,G,I) == me ) 963 AND local_receiver_exclude(S,G,I) } 965 The clause "local_receiver_include(S,G,I)" is true if the IGMP/MLD 966 module or other local membership mechanism has determined that there are 967 local members on interface I that desire to receive traffic sent 968 specifically by S to G. "local_receiver_include(*,G,I)" is true if the 969 IGMP/MLD module or other local membership mechanism has determined that 970 there are local members on interface I that desire to receive all 971 traffic sent to G. "local_receiver_exclude(S,G,I) is true if 972 "local_receiver_include(*,G,I)" is true but none of the local members 973 desire to receive traffic from S. 975 The set "joins(*,*,RP)" is the set of all interfaces on which the router 976 has received (*,*,RP) Joins: 978 joins(*,*,RP) = 979 { all interfaces I such that 980 DownstreamJPState(*,*,RP,I) is either Join or 981 Prune-Pending } 983 DownstreamJPState(*,*,RP,I) is the state of the finite state machine in 984 Section 4.5.1. 986 The set "joins(*,G)" is the set of all interfaces on which the router 987 has received (*,G) Joins: 989 joins(*,G) = 990 { all interfaces I such that 991 DownstreamJPState(*,G,I) is either Join or Prune-Pending } 993 DownstreamJPState(*,G,I) is the state of the finite state machine in 994 Section 4.5.2. 996 The set "joins(S,G)" is the set of all interfaces on which the router 997 has received (S,G) Joins: 999 joins(S,G) = 1000 { all interfaces I such that 1001 DownstreamJPState(S,G,I) is either Join or Prune-Pending } 1003 DownstreamJPState(S,G,I) is the state of the finite state machine in 1004 Section 4.5.3. 1006 The set "prunes(S,G,rpt)" is the set of all interfaces on which the 1007 router has received (*,G) joins and (S,G,rpt) prunes. 1009 prunes(S,G,rpt) = 1010 { all interfaces I such that 1011 DownstreamJPState(S,G,rpt,I) is Prune or PruneTmp } 1013 DownstreamJPState(S,G,rpt,I) is the state of the finite state machine in 1014 Section 4.5.4. 1016 The set "lost_assert(*,G)" is the set of all interfaces on which the 1017 router has received (*,G) joins but has lost a (*,G) assert. The macro 1018 lost_assert(*,G,I) is defined in Section 4.6.5. 1020 lost_assert(*,G) = 1021 { all interfaces I such that 1022 lost_assert(*,G,I) == TRUE } 1024 The set "lost_assert(S,G,rpt)" is the set of all interfaces on which the 1025 router has received (*,G) joins but has lost an (S,G) assert. The macro 1026 lost_assert(S,G,rpt,I) is defined in Section 4.6.5. 1028 lost_assert(S,G,rpt) = 1029 { all interfaces I such that 1030 lost_assert(S,G,rpt,I) == TRUE } 1032 The set "lost_assert(S,G)" is the set of all interfaces on which the 1033 router has received (S,G) joins but has lost an (S,G) assert. The macro 1034 lost_assert(S,G,I) is defined in Section 4.6.5. 1036 lost_assert(S,G) = 1037 { all interfaces I such that 1038 lost_assert(S,G,I) == TRUE } 1040 The following pseudocode macro definitions are also used in many places 1041 in the specification. Basically RPF' is the RPF neighbor towards an RP 1042 or source unless a PIM-Assert has overridden the normal choice of 1043 neighbor. 1045 neighbor RPF'(*,G) { 1046 if ( I_Am_Assert_Loser(*, G, RPF_interface(RP(G))) ) { 1047 return AssertWinner(*, G, RPF_interface(RP(G)) ) 1048 } else { 1049 return NBR( RPF_interface(RP(G)), MRIB.next_hop( RP(G) ) ) 1050 } 1051 } 1053 neighbor RPF'(S,G,rpt) { 1054 if( I_Am_Assert_Loser(S, G, RPF_interface(RP(G)) ) ) { 1055 return AssertWinner(S, G, RPF_interface(RP(G)) ) 1056 } else { 1057 return RPF'(*,G) 1058 } 1059 } 1061 neighbor RPF'(S,G) { 1062 if ( I_Am_Assert_Loser(S, G, RPF_interface(S) )) { 1063 return AssertWinner(S, G, RPF_interface(S) ) 1064 } else { 1065 return NBR( RPF_interface(S), MRIB.next_hop( S ) ) 1066 } 1067 } 1069 RPF'(*,G) and RPF'(S,G) indicate the neighbor from which data packets 1070 should be coming and to which joins should be sent on the RP tree and 1071 SPT respectively. 1073 RPF'(S,G,rpt) is basically RPF'(*,G) modified by the result of an 1074 Assert(S,G) on RPF_interface(RP(G)). In such a case, packets from S 1075 will be originating from a different router than RPF'(*,G). If we only 1076 have active (*,G) Join state, we need to accept packets from 1077 RPF'(S,G,rpt), and add a Prune(S,G,rpt) to the periodic Join(*,G) 1078 messages that we send to RPF'(*,G) (See Section 4.5.8). 1080 The function MRIB.next_hop( S ) returns an address of the next-hop PIM 1081 neighbor toward the host S, as indicated by the current MRIB. If S is 1082 directly adjacent, then MRIB.next_hop( S ) returns NULL. At the RP for 1083 G, MRIB.next_hop( RP(G)) returns NULL. 1085 The function NBR( I, A ) uses information gathered through PIM Hello 1086 messages to map the IP address A of a directly connected PIM neighbor 1087 router on interface I to the primary IP address of the same router 1088 (Section 4.3.4). The primary IP address of a neighbor is the address | 1089 that it uses as the source of its PIM Hello messages. Note that a 1090 neighbor's IP address may be non-unique within the PIM neighbor database 1091 due to scope issues. The address must however be unique amongst the 1092 addresses of all the PIM neighbors on a specific interface. 1094 I_Am_Assert_Loser(S, G, I) is true if the Assert state machine (in | 1095 Section 4.6.1) for (S,G) on Interface I is in "I am Assert Loser" state. 1097 I_Am_Assert_Loser(*, G, I) is true if the Assert state machine (in | 1098 Section 4.6.2) for (*,G) on Interface I is in "I am Assert Loser" state. 1100 4.2. Data Packet Forwarding Rules 1102 The PIM-SM packet forwarding rules are defined below in pseudocode. 1104 iif is the incoming interface of the packet. 1105 S is the source address of the packet. 1106 G is the destination address of the packet (group address). 1107 RP is the address of the Rendezvous Point for this group. 1108 RPF_interface(S) is the interface the MRIB indicates would be used 1109 to route packets to S. 1110 RPF_interface(RP) is the interface the MRIB indicates would be used 1111 to route packets to RP, except at the RP when it is the 1112 decapsulation interface (the "virtual" interface on which register 1113 packets are received). 1115 First, we restart (or start) the Keepalive Timer if the source is on a 1116 directly connected subnet. 1118 Second, we check to see if the SPTbit should be set because we've now | 1119 switched from the RP tree to the SPT. 1121 Next we check to see whether the packet should be accepted based on TIB 1122 state and the interface that the packet arrived on. 1124 If the packet should be forwarded using (S,G) state, we then build an 1125 outgoing interface list for the packet. If this list is not empty, then 1126 we restart the (S,G) state Keepalive Timer. 1128 If the packet should be forwarded using (*,*,RP) or (*,G) state, then we 1129 just build an outgoing interface list for the packet. We also check if 1130 we should initiate a switch to start receiving this source on a shortest 1131 path tree. 1133 Finally we remove the incoming interface from the outgoing interface 1134 list we've created, and if the resulting outgoing interface list is not 1135 empty, we forward the packet out of those interfaces. 1137 On receipt of data from S to G on interface iif: 1138 if( DirectlyConnected(S) == TRUE AND iif == RPF_interface(S) ) { | 1139 set KeepaliveTimer(S,G) to Keepalive_Period 1140 # Note: a register state transition or UpstreamJPState(S,G) 1141 # transition may happen as a result of restarting 1142 # KeepaliveTimer, and must be dealt with here. 1143 } 1145 Update_SPTbit(S,G,iif) 1146 oiflist = NULL 1148 if( iif == RPF_interface(S) AND UpstreamJPState(S,G) == Joined ) { 1149 oiflist = inherited_olist(S,G) 1150 if( oiflist != NULL ) { 1151 set KeepaliveTimer(S,G) to Keepalive_Period 1152 } 1153 } else if( iif == RPF_interface(RP(G)) AND SPTbit(S,G) == FALSE) { 1154 oiflist = inherited_olist(S,G,rpt) 1155 CheckSwitchToSpt(S,G) 1156 } else { 1157 # Note: RPF check failed 1158 if ( SPTbit(S,G) == TRUE AND iif is in inherited_olist(S,G) ) { 1159 send Assert(S,G) on iif 1160 } else if ( SPTbit(S,G) == FALSE AND 1161 iif is in inherited_olist(S,G,rpt) { 1162 send Assert(*,G) on iif 1163 } 1164 } 1166 oiflist = oiflist (-) iif 1167 forward packet on all interfaces in oiflist 1169 This pseudocode employs several "macro" definitions: 1171 DirectlyConnected(S) is TRUE if the source S is on any subnet that is 1172 directly connected to this router (or for packets originating on this 1173 router). 1175 inherited_olist(S,G) and inherited_olist(S,G,rpt) are defined in Section 1176 4.1. 1178 Basically inherited_olist(S,G) is the outgoing interface list for 1179 packets forwarded on (S,G) state taking into account (*,*,RP) state, 1180 (*,G) state, asserts, etc. 1182 inherited_olist(S,G,rpt) is the outgoing interface for packets forwarded 1183 on (*,*,RP) or (*,G) state taking into account (S,G,rpt) prune state, 1184 and asserts, etc. 1186 Update_SPTbit(S,G,iif) is defined in Section 4.2.2. 1188 CheckSwitchToSpt(S,G) is defined in Section 4.2.1. 1190 UpstreamJPState(S,G) is the state of the finite state machine in Section 1191 4.5.7. 1193 Keepalive_Period is defined in Section 4.10. 1195 Data triggered PIM-Assert messages sent from the above forwarding code 1196 should be rate-limited in a implementation-dependent manner. 1198 4.2.1. Last-hop Switchover to the SPT 1200 In Sparse-Mode PIM, last-hop routers join the shared tree towards the 1201 RP. Once traffic from sources to joined groups arrives at a last-hop 1202 router it has the option of switching to receive the traffic on a 1203 shortest path tree (SPT). 1205 The decision for a router to switch to the SPT is controlled as follows: 1207 void 1208 CheckSwitchToSpt(S,G) { 1209 if ( ( pim_include(*,G) (-) pim_exclude(S,G) 1210 (+) pim_include(S,G) != NULL ) 1211 AND SwitchToSptDesired(S,G) ) { 1212 # Note: Restarting the KAT will result in the SPT switch | 1213 restart KeepaliveTimer(S,G); 1214 } 1215 } 1217 SwitchToSptDesired(S,G) is a policy function that is implementation 1218 defined. An "infinite threshold" policy can be implemented making 1219 SwitchToSptDesired(S,G) return false all the time. A "switch on first 1220 packet" policy can be implemented by making SwitchToSptDesired(S,G) 1221 return true once a single packet has been received for the source and 1222 group. 1224 4.2.2. Setting and Clearing the (S,G) SPTbit 1226 The (S,G) SPTbit is used to distinguish whether to forward on 1227 (*,*,RP)/(*,G) or on (S,G) state. When switching from the RP tree to 1228 the source tree, there is a transition period when data is arriving due 1229 to upstream (*,*,RP)/(*,G) state while upstream (S,G) state is being 1230 established during which time a router should continue to forward only 1231 on (*,*,RP)/(*,G) state. This prevents temporary black-holes that would 1232 be caused by sending a Prune(S,G,rpt) before the upstream (S,G) state 1233 has finished being established. 1235 Thus, when a packet arrives, the (S,G) SPTbit is updated as follows: 1237 void 1238 Update_SPTbit(S,G,iif) { 1239 if ( iif == RPF_interface(S) 1240 AND JoinDesired(S,G) == TRUE 1241 AND ( DirectlyConnected(S) == TRUE 1242 OR RPF_interface(S) != RPF_interface(RP(G)) 1243 OR inherited_olist(S,G,rpt) == NULL 1244 OR ( ( RPF'(S,G) == RPF'(*,G) ) AND 1245 ( RPF'(S,G) != NULL ) ) | 1246 OR ( I_Am_Assert_Loser(S,G,iif) ) { | 1247 Set SPTbit(S,G) to TRUE 1248 } 1249 } 1251 Additionally a router can set SPTbit(S,G) to TRUE in other cases, such 1252 as when it receives an Assert(S,G) on RPF_interface(S) (see Section 1253 4.6.1). 1255 JoinDesired(S,G) is defined in Section 4.5.7, and indicates whether we 1256 have the appropriate (S,G) Join state to wish to send a Join(S,G) 1257 upstream. 1259 Basically Update_SPTbit will set the SPTbit if we have the appropriate | 1260 (S,G) join state and the packet arrived on the correct upstream 1261 interface for S, and one or more of the following conditions applies: 1263 1. The source is directly connected, in which case the switch to the 1264 SPT is a no-op. 1266 2. The RPF interface to S is different from the RPF interface to the 1267 RP. The packet arrived on RPF_interface(S), and so the SPT must 1268 have been completed. 1270 3. No-one wants the packet on the RP tree. 1272 4. RPF'(S,G) == RPF'(*,G). In this case the router will never be able 1273 to tell if the SPT has been completed, so it should just switch 1274 immediately. 1276 In the case where the RPF interface is the same for the RP and for S, 1277 but RPF'(S,G) and RPF'(*,G) differ, then we wait for an Assert(S,G) 1278 which indicates that the upstream router with (S,G) state believes the 1279 SPT has been completed. However item (3) above is needed because there 1280 may not be any (*,G) state to trigger an Assert(S,G) to happen. 1282 The SPTbit is cleared in the (S,G) upstream state machine (see Section | 1283 4.5.7) when JoinDesired(S,G) becomes FALSE. 1285 4.3. Designated Routers (DR) and Hello Messages 1287 A shared-media LAN like Ethernet may have multiple PIM-SM routers | 1288 connected to it. A single one of these routers, the DR, will act on | 1289 behalf of directly connected hosts with respect to the PIM-SM protocol. | 1290 Because the distinction between LANs and point-to-point interfaces can | 1291 sometimes be blurred, and because routers may also have multicast host | 1292 functionality, the PIM-SM specification makes no distinction between the | 1293 two. Thus DR election will happen on all interfaces, LAN or otherwise. 1295 DR election is performed using Hello messages. Hello messages are also 1296 the way that option negotiation takes place in PIM, so that additional 1297 functionality can be enabled, or parameters tuned. 1299 4.3.1. Sending Hello Messages 1301 PIM Hello messages are sent periodically on each PIM-enabled interface. | 1302 They allow a router to learn about the neighboring PIM routers on each 1303 interface. Hello messages are also the mechanism used to elect a 1304 Designated Router (DR), and to negotiate additional capabilities. A 1305 router must record the Hello information received from each PIM 1306 neighbor. 1308 Hello messages MUST be sent on all active interfaces, including physical 1309 point-to-point links, and are multicast to the `ALL-PIM-ROUTERS' group 1310 address (`224.0.0.13' for IPv4 and `ff02::d' for IPv6). 1312 We note that some implementations do not send Hello messages 1313 on point-to-point interfaces. This is non-compliant behavior. 1314 A compliant PIM router MUST send Hello messages, even on 1315 point-to-point interfaces. 1317 A per interface Hello Timer (HT(I)) is used to trigger sending Hello 1318 messages on each active interface. When PIM is enabled on an interface 1319 or a router first starts, the Hello Timer of that interface is set to a 1320 random value between 0 and Triggered_Hello_Delay. This prevents 1321 synchronization of Hello messages if multiple routers are powered on 1322 simultaneously. After the initial randomized interval, Hello messages 1323 must be sent every Hello_Period seconds. The Hello Timer should not be 1324 reset except when it expires. 1326 Note that neighbors will not accept Join/Prune or Assert messages from a 1327 router unless they have first heard a Hello message from that router. 1328 Thus if a router needs to send a Join/Prune or Assert message on an 1329 interface on which it has not yet sent a Hello message with the 1330 currently configured IP address, then it MUST immediately send the 1331 relevant Hello message without waiting for the Hello Timer to expire, 1332 followed by the Join/Prune or Assert message. 1334 The DR_Priority Option allows a network administrator to give preference 1335 to a particular router in the DR election process by giving it a 1336 numerically larger DR Priority. The DR_Priority Option SHOULD be 1337 included in every Hello message, even if no DR Priority is explicitly 1338 configured on that interface. This is necessary because priority-based 1339 DR election is only enabled when all neighbors on an interface advertise 1340 that they are capable of using the DR_Priority Option. The default 1341 priority is 1. 1343 The Generation_Identifier (GenID) Option SHOULD be included in all Hello 1344 messages. The GenID option contains a randomly generated 32-bit value 1345 that is regenerated each time PIM forwarding is started or restarted on 1346 the interface, including when the router itself restarts. When a Hello 1347 message with a new GenID is received from a neighbor, any old Hello 1348 information about that neighbor SHOULD be discarded and superseded by 1349 the information from the new Hello message. This may cause a new DR to 1350 be chosen on that interface. 1352 The LAN Prune Delay Option SHOULD be included in all Hello messages sent 1353 on multi-access LANs. This option advertises a router's capability to 1354 use values other than the default for the Propagation_Delay and 1355 Override_Interval which affect the setting of the Prune-Pending, 1356 Upstream Join and Override Timers (defined in Section 4.10). 1358 The Interface_Address_List Option advertises all the secondary addresses 1359 associated with the source interface of the router originating the 1360 message. The option MUST be included in all Hello messages if there are 1361 secondary addresses associated with the source interface and MAY be 1362 omitted if no secondary addresses exist. 1364 To allow new or rebooting routers to learn of PIM neighbors quickly, 1365 when a Hello message is received from a new neighbor, or a Hello message 1366 with a new GenID is received from an existing neighbor, a new Hello 1367 message should be sent on this interface after a randomized delay 1368 between 0 and Triggered_Hello_Delay. This triggered message need not 1369 change the timing of the scheduled periodic message. If a router needs 1370 to send a Join/Prune to the new neighbor or send an Assert message in 1371 response to an Assert message from the new neighbor before this 1372 randomized delay has expired, then it MUST immediately send the relevant 1373 Hello message without waiting for the Hello Timer to expire, followed by 1374 the Join/Prune or Assert message. If it does not do this, then the new 1375 neighbor will discard the Join/Prune or Assert message. 1377 Before an interface goes down or changes primary IP address, a Hello 1378 message with a zero HoldTime should be sent immediately (with the old IP 1379 address if the IP address changed). This will cause PIM neighbors to 1380 remove this neighbor (or its old IP address) immediately. After an 1381 interface has changed its IP address, it MUST send a Hello message with 1382 its new IP address. If an interface changes one of its secondary IP 1383 addresses, a Hello message with an updated Address_List option and a 1384 non-zero HoldTime should be sent immediately. This will cause PIM 1385 neighbors to update this neighbor's list of secondary addresses 1386 immediately. 1388 4.3.2. DR Election 1390 When a PIM Hello message is received on interface I the following | 1391 information about the sending neighbor is recorded: 1393 neighbor.interface 1394 The interface on which the Hello message arrived. 1396 neighbor.primary_ip_address 1397 The IP address that the PIM neighbor used as the source 1398 address of the Hello message. 1400 neighbor.genid 1401 The Generation ID of the PIM neighbor. 1403 neighbor.dr_priority 1404 The DR Priority field of the PIM neighbor if it is present in 1405 the Hello message. 1407 neighbor.dr_priority_present 1408 A flag indicating if the DR Priority field was present in the 1409 Hello message. 1411 neighbor.timeout 1412 A timer value to time out the neighbor state when it becomes 1413 stale. 1414 The Neighbor Liveness Timer (NLT(N,I)) is reset to 1415 Hello_Holdtime (from the Hello Holdtime option) whenever a 1416 Hello message is received containing a Holdtime option, or to 1417 Default_Hello_Holdtime if the Hello message does not contain 1418 the Holdtime option. 1420 Neighbor state is deleted when the neighbor timeout expires. 1422 The function for computing the DR on interface I is: 1424 host 1425 DR(I) { 1426 dr = me 1427 for each neighbor on interface I { 1428 if ( dr_is_better( neighbor, dr, I ) == TRUE ) { 1429 dr = neighbor 1430 } 1431 } 1432 return dr 1433 } 1435 The function used for comparing DR "metrics" on interface I is: 1437 bool 1438 dr_is_better(a,b,I) { 1439 if( there is a neighbor n on I for which n.dr_priority_present 1440 is false ) { 1441 return a.primary_ip_address > b.primary_ip_address 1442 } else { 1443 return ( a.dr_priority > b.dr_priority ) OR 1444 ( a.dr_priority == b.dr_priority AND 1445 a.primary_ip_address > b.primary_ip_address ) 1446 } 1447 } 1449 The trivial function I_am_DR(I) is defined to aid readability: 1451 bool 1452 I_am_DR(I) { 1453 return DR(I) == me 1454 } 1456 The DR Priority is a 32-bit unsigned number and the numerically larger 1457 priority is always preferred. A router's idea of the current DR on an 1458 interface can change when a PIM Hello message is received, when a | 1459 neighbor times out, or when a router's own DR Priority changes. If the 1460 router becomes the DR or ceases to be the DR, this will normally cause 1461 the DR Register state machine to change state. Subsequent actions are 1462 determined by that state machine. 1464 We note that some PIM implementations do not send Hello 1465 messages on point-to-point interfaces, and so cannot perform 1466 DR election on such interfaces. This in non-compliant 1467 behavior. DR election MUST be performed on ALL active PIM-SM 1468 interfaces. 1470 4.3.3. Reducing Prune Propagation Delay on LANs 1472 In addition to the information recorded for the DR Election, the 1473 following per neighbor information is obtained from the LAN Prune Delay 1474 Hello option: 1476 neighbor.lan_prune_delay_present 1477 A flag indicating if the LAN Prune Delay option was present in 1478 the Hello message. 1480 neighbor.tracking_support 1481 A flag storing the value of the T bit in the LAN Prune Delay 1482 option if it is present in the Hello message. This indicates 1483 the neighbor's capability to disable Join message suppression. | 1485 neighbor.propagation_delay | 1486 The Propagation Delay field of the LAN Prune Delay option (if | 1487 present) in the Hello message. 1489 neighbor.override_interval 1490 The Override_Interval field of the LAN Prune Delay option (if 1491 present) in the Hello message. 1493 The additional state described above is deleted along with the DR 1494 neighbor state when the neighbor timeout expires. 1496 Just like the DR_Priority option, the information provided in the LAN 1497 Prune Delay option is not used unless all neighbors on a link advertise 1498 the option. The function below computes this state: 1500 bool 1501 lan_delay_enabled(I) { 1502 for each neighbor on interface I { 1503 if ( neighbor.lan_prune_delay_present == false ) { 1504 return false 1505 } 1506 } 1507 return true 1508 } 1510 The Propataion Delay inserted by a router in the LAN Prune Delay option | 1511 expresses the expected message propagation delay on the link and should 1512 be configurable by the system administrator. It is used by upstream 1513 routers to figure out how long they should wait for a Join override 1514 message before pruning an interface. 1516 PIM implementors should enforce a lower bound on the permitted values 1517 for this delay to allow for scheduling and processing delays within 1518 their router. Such delays may cause received messages to be processed 1519 later as well as triggered messages to be sent later than intended. | 1520 Setting this Propagation Delay to too low a value may result in 1521 temporary forwarding outages because a downstream router will not be 1522 able to override a neighbor's Prune message before the upstream neighbor 1523 stops forwarding. 1525 When all routers on a link are in a position to negotiate a different 1526 than default Propagation Delay, the largest value from those advertised 1527 by each neighbor is chosen. The function for computing the | 1528 Effective_Propagation_Delay of interface I is: 1530 time_interval 1531 Effective_Propagation_Delay(I) { | 1532 if ( lan_delay_enabled(I) == false ) { 1533 return Propagation_delay_default | 1534 } 1535 delay = Propagation_Delay(I) | 1536 for each neighbor on interface I { 1537 if ( neighbor.propagation_delay > delay ) { | 1538 delay = neighbor.propagation_delay | 1539 } 1540 } 1541 return delay 1542 } 1544 To avoid synchronization of override messages when multiple downstream 1545 routers share a multi-access link, sending of such messages is delayed 1546 by a small random amount of time. The period of randomization should 1547 represent the size of the PIM router population on the link. Each 1548 router expresses its view of the amount of randomization necessary in | 1549 the Override Interval field of the LAN Prune Delay option. 1551 When all routers on a link are in a position to negotiate a different | 1552 than default Override Interval, the largest value from those advertised | 1553 by each neighbor is chosen. The function for computing the Effective | 1554 Override Interval of interface I is: 1556 time_interval 1557 Effective_Override_Interval(I) { | 1558 if ( lan_delay_enabled(I) == false ) { 1559 return t_override_default 1560 } 1561 delay = Override_Interval(I) | 1562 for each neighbor on interface I { 1563 if ( neighbor.override_interval > delay ) { 1564 delay = neighbor.override_interval 1565 } 1566 } 1567 return delay 1568 } 1570 Although the mechanisms are not specified in this document, it is 1571 possible for upstream routers to explicitly track the join membership of 1572 individual downstream routers if Join suppression is disabled. A router 1573 can advertise its willingness to disable Join suppression by using the T 1574 bit in the LAN Prune Delay Hello option. Unless all PIM routers on a 1575 link negotiate this capability, explicit tracking and the disabling of 1576 the Join suppression mechanism are not possible. The function for 1577 computing the state of Suppression on interface I is: 1579 bool 1580 Suppression_Enabled(I) { 1581 if ( lan_delay_enabled(I) == false ) { 1582 return true 1583 } 1584 for each neighbor on interface I { 1585 if ( neighbor.tracking_support == false ) { 1586 return true 1587 } 1588 } 1589 return false 1590 } 1592 Note that the setting of Suppression_Enabled(I) affects the value of 1593 t_suppressed (see Section 4.10). 1595 4.3.4. Maintaining Secondary Address Lists 1597 Communication of a router's interface secondary addresses to its PIM 1598 neighbors is necessary to provide the neighbors with a mechanism for 1599 mapping next_hop information obtained through their MRIB to a primary 1600 address that can be used as a destination for Join/Prune messages. The 1601 mapping is performed through the NBR macro. The primary address of a 1602 PIM neighbor is obtained from the source IP address used in its PIM 1603 Hello messages. Secondary addresses are carried within the Hello message 1604 in an Address List Hello option. The primary address of the source 1605 interface of the router MUST NOT be listed within the Address List Hello 1606 option. 1608 In addition to the information recorded for the DR Election, the 1609 following per neighbor information is obtained from the Address List 1610 Hello option: 1612 neighbor.secondary_address_list 1613 The list of secondary addresses used by the PIM neighbor on 1614 the interface through which the Hello message was transmitted. 1616 When processing a received PIM Hello message containing an Address List 1617 Hello option, the list of secondary addresses in the message completely 1618 replaces any previously associated secondary addresses for that 1619 neighbor. If a received PIM Hello message does not contain an Address 1620 List Hello option then all secondary addresses associated with the 1621 neighbor must be deleted. If a received PIM Hello message contains an 1622 Address List Hello option that includes the primary address of the 1623 sending router in the list of secondary addresses (although this is not 1624 expected) then the addresses listed in the message excluding the primary 1625 address are used to update the associated secondary addresses for that 1626 neighbor. 1628 All the advertised secondary addresses in received Hello messages must 1629 be checked against those previously advertised by all other PIM 1630 neighbors on that interface. If there is a conflict and the same 1631 secondary address was previously advertised by another neighbor then 1632 only the most recently received mapping MUST be maintained and an error 1633 message SHOULD be logged to the administrator in a rate limited manner. 1635 Within one Address List Hello option, all the addresses MUST be of the 1636 same address family. It is not permitted to mix IPv4 and IPv6 addresses 1637 within the same message. In addition, the address family of the fields 1638 in the message SHOULD be the same as the IP source and destination 1639 addresses of the packet header. 1641 4.4. PIM Register Messages 1643 Overview 1645 The Designated Router (DR) on a LAN or point-to-point link encapsulates 1646 multicast packets from local sources to the RP for the relevant group 1647 unless it recently received a Register-Stop message for that (S,G) or 1648 (*,G) from the RP. When the DR receives a Register-Stop message from 1649 the RP, it starts a Register-Stop Timer to maintain this state. Just 1650 before the Register-Stop Timer expires, the DR sends a Null-Register 1651 Message to the RP to allow the RP to refresh the Register-Stop 1652 information at the DR. If the Register-Stop Timer actually expires, the 1653 DR will resume encapsulating packets from the source to the RP. 1655 4.4.1. Sending Register Messages from the DR 1657 Every PIM-SM router has the capability to be a DR. The state machine 1658 below is used to implement Register functionality. For the purposes of 1659 specification, we represent the mechanism to encapsulate packets to the 1660 RP as a Register-Tunnel interface, which is added to or removed from the 1661 (S,G) olist. The tunnel interface then takes part in the normal packet 1662 forwarding rules as specified in Section 4.2. 1664 If register state is maintained, it is maintained only for directly 1665 connected sources, and is per-(S,G). There are four states in the DR's 1666 per-(S,G) Register state machine: 1668 Join (J) 1669 The register tunnel is "joined" (the join is actually implicit, but 1670 the DR acts as if the RP has joined the DR on the tunnel 1671 interface). 1673 Prune (P) 1674 The register tunnel is "pruned" (this occurs when a Register-Stop 1675 is received). 1677 Join-Pending (JP) 1678 The register tunnel is pruned but the DR is contemplating adding it 1679 back. 1681 NoInfo (NI) 1682 No information. This is the initial state, and the state when the 1683 router is not the DR. 1685 In addition, a Register-Stop Timer (RST) is kept if the state machine is 1686 not in the NoInfo state. 1688 Figure 1: Per-(S,G) register state machine at a DR in tabular form 1690 +-----------++---------------------------------------------------------------+ 1691 | || Event | 1692 | ++-----------+------------+------------+------------+------------+ 1693 |Prev State ||Register- | Could | Could | Register- | RP changed | 1694 | ||Stop Timer | Register | Register | Stop | | 1695 | ||expires | ->True | ->False | received | | 1696 +-----------++-----------+------------+------------+------------+------------+ 1697 |NoInfo ||- | -> J state | - | - | - | 1698 |(NI) || | add reg | | | | 1699 | || | tunnel | | | | 1700 +-----------++-----------+------------+------------+------------+------------+ 1701 | ||- | - | -> NI | -> P state | -> J state | 1702 | || | | state | | | 1703 | || | | remove reg | remove reg | update reg | 1704 |Join (J) || | | tunnel | tunnel; | tunnel | 1705 | || | | | set | | 1706 | || | | | Register- | | 1707 | || | | | Stop | | 1708 | || | | | Timer(*) | | 1709 +-----------++-----------+------------+------------+------------+------------+ 1710 | ||-> J state | - | -> NI | -> P state | -> J state | 1711 | || | | state | | | 1712 |Join- ||add reg | | | set | add reg | 1713 |Pending ||tunnel | | | Register- | tunnel; | 1714 |(JP) || | | | Stop | cancel | 1715 | || | | | Timer(*) | Register- | 1716 | || | | | | Stop Timer | 1717 Tim+-----------++-----------+------------+------------+------------+------------+ 1718 | ||-> JP | - | -> NI | - | -> J state | 1719 | ||state | | state | | | 1720 | ||set | | | | add reg | 1721 |Prune (P) ||Register- | | | | tunnel; | 1722 | ||Stop | | | | cancel | 1723 | ||Timer(**); | | | | Register- | 1724 | ||send Null- | | | | Stop Timer | 1725 | ||Register | | | | | 1726 +-----------++-----------+------------+------------+------------+------------+ 1728 Notes: 1730 (*) The Register-Stop Timer is set to a random value chosen uniformly 1731 from the interval ( 0.5 * Register_Suppression_Time, 1.5 * 1732 Register_Suppression_Time) minus Register_Probe_Time; 1734 Subtracting off Register_Probe_Time is a bit unnecessary because it 1735 is really small compared to Register_Suppression_Time, but was in 1736 the old spec and is kept for compatibility. 1738 (**) The Register-Stop Timer is set to Register_Probe_Time. 1740 The following actions are defined: 1742 Add Register Tunnel 1744 A Register-Tunnel virtual interface, VI, is created (if it doesn't 1745 already exist) with its encapsulation target being RP(G). 1746 DownstreamJPState(S,G,VI) is set to Join state, causing the tunnel 1747 interface to be added to immediate_olist(S,G). 1749 Remove Register Tunnel 1751 VI is the Register-Tunnel virtual interface with encapsulation target of 1752 RP(G). DownstreamJPState(S,G,VI) is set to NoInfo state, causing the 1753 tunnel interface to be removed from immediate_olist(S,G). If 1754 DownstreamJPState(S,G,VI) is NoInfo for all (S,G), then VI can be 1755 deleted. 1757 Update Register Tunnel 1759 This action occurs when RP(G) changes. 1761 VI_old is the Register-Tunnel virtual interface with encapsulation 1762 target old_RP(G). A Register-Tunnel virtual interface, VI_new, is 1763 created (if it doesn't already exist) with its encapsulation target 1764 being new_RP(G). DownstreamJPState(S,G,VI_old) is set to NoInfo state 1765 and DownstreamJPState(S,G,VI_new) is set to Join state. If 1766 DownstreamJPState(S,G,VI_old) is NoInfo for all (S,G), then VI_old can 1767 be deleted. 1769 Note that we can not simply change the encapsulation target of VI_old 1770 because not all groups using that encapsulation tunnel will have moved 1771 to the same new RP. 1773 CouldRegister(S,G) 1775 The macro "CouldRegister" in the state machine is defined as: 1777 bool CouldRegister(S,G) { 1778 return ( I_am_DR( RPF_interface(S) ) AND 1779 KeepaliveTimer(S,G) is running AND 1780 DirectlyConnected(S) == TRUE ) 1781 } 1783 Note that on reception of a packet at the DR from a directly connected 1784 source, KeepaliveTimer(S,G) needs to be set by the packet forwarding 1785 rules before computing CouldRegister(S,G) in the register state machine, 1786 or the first packet from a source won't be registered. 1788 Encapsulating data packets in the Register Tunnel 1790 Conceptually, the Register Tunnel is an interface with a smaller MTU 1791 than the underlying IP interface towards the RP. IP fragmentation on 1792 packets forwarded on the Register Tunnel is performed based upon this | 1793 smaller MTU. The encapsulating DR may perform Path MTU Discovery to the 1794 RP to determine the effective MTU of the tunnel. Fragmentation for the | 1795 smaller MTU should take both the outer IP header and the PIM register 1796 header overhead into account. If a multicast packet is fragmented on 1797 the way into the Register Tunnel, each fragment is encapsulated 1798 individually so it contains IP, PIM, and inner IP headers. 1800 In IPv6, the DR MUST perform Path MTU discovery, and an ICMP Packet Too | 1801 Big message MUST be sent by the encapsulating DR if it receives a packet 1802 that will not fit in the effective MTU of the tunnel. If the MTU 1803 between the DR and the RP results in the effective tunnel MTU being 1804 smaller than 1280 (the IPv6 minimum MTU), the DR MUST send Fragmentation 1805 Required messages with an MTU value of 1280 and MUST fragment its PIM 1806 register messages as required, using an IPv6 fragmentation header 1807 between the outer IPv6 header and the PIM Register header. 1809 The TTL of a forwarded data packet is decremented before it is | 1810 encapsulated in the Register Tunnel. The encapsulating packet uses the 1811 normal TTL that the router would use for any locally-generated IP 1812 packet. 1814 The IP ECN bits should be copied from the original packet to the IP 1815 header of the encapsulating packet. They SHOULD NOT be set 1816 independently by the encapsulating router. 1818 The Diffserv Code Point (DSCP) should be copied from the original packet 1819 to the IP header of the encapsulating packet. It MAY be set 1820 independently by the encapsulating router, based upon static 1821 configuration or traffic classification. See [10] for more discussion 1822 on setting the DSCP on tunnels. 1824 Handling Register-Stop(*,G) Messages at the DR 1826 An old RP might send a Register-Stop message with the source address set 1827 to all-zeros. This was the normal course of action in RFC 2326 when the 1828 Register message matched against (*,G) state at the RP, and was defined 1829 as meaning "stop encapsulating all sources for this group". However, 1830 the behavior of such a Register-Stop(*,G) is ambiguous or incorrect in 1831 some circumstances. 1833 We specify that an RP should not send Register-Stop(*,G) messages, but 1834 for compatibility, a DR should be able to accept one if it is received. 1836 A Register-Stop(*,G) should be treated as a Register-Stop(S,G) for all 1837 (S,G) Register state machines that are not in the NoInfo state. A 1838 router should not apply a Register-Stop(*,G) to sources that become 1839 active after the Register-Stop(*,G) was received. 1841 4.4.2. Receiving Register Messages at the RP 1843 When an RP receives a Register message, the course of action is decided 1844 according to the following pseudocode: 1846 packet_arrives_on_rp_tunnel( pkt ) { 1847 if( outer.dst is not one of my addresses ) { 1848 drop the packet silently. 1849 # Note: this may be a spoofing attempt | 1850 } 1851 if( I_am_RP(G) AND outer.dst == RP(G) ) { 1852 sentRegisterStop = FALSE; | 1853 if ( register.borderbit == TRUE ) { | 1854 if ( PMBR(S,G) == unknown ) { | 1855 PMBR(S,G) = outer.src | 1856 } else if ( outer.src != PMBR(S,G) ) { | 1857 send Register-Stop(S,G) to outer.src | 1858 drop the packet silently. | 1859 } | 1860 } | 1861 if ( SPTbit(S,G) OR 1862 ( SwitchToSptDesired(S,G) AND ( inherited_olist(S,G) == NULL ))) { 1863 send Register-Stop(S,G) to outer.src 1864 sentRegisterStop = TRUE; 1865 } 1866 if ( SPTbit(S,G) OR SwitchToSptDesired(S,G) ) { 1867 if ( sentRegisterStop == TRUE ) { 1868 restart KeepaliveTimer(S,G) to RP_Keepalive_Period; 1869 } else { | 1870 restart KeepaliveTimer(S,G) to Keepalive_Period; | 1871 } 1872 } 1873 if( !SPTbit(S,G) AND ! pkt.NullRegisterBit ) { 1874 decapsulate and forward the inner packet to | 1875 inherited_olist(S,G,rpt) # Note (+) | 1876 } 1877 } else { 1878 send Register-Stop(S,G) to outer.src 1879 # Note (*) 1880 } 1881 } 1883 outer.dst is the IP destination address of the encapsulating header. 1885 outer.src is the IP source address of the encapsulating header, i.e., 1886 the DR's address. 1888 I_am_RP(G) is true if the group-to-RP mapping indicates that this router 1889 is the RP for the group. 1891 Note (*): This may block traffic from S for Register_Suppression_Time if 1892 the DR learned about a new group-to-RP mapping before the RP did. 1893 However, this doesn't matter unless we figure out some way for the 1894 RP to also accept (*,G) joins when it doesn't yet realize that it 1895 is about to become the RP for G. This will all get sorted out once 1896 the RP learns the new group-to-rp mapping. We decided to do 1897 nothing about this and just accept the fact that PIM may suffer 1898 interrupted (*,G) connectivity following an RP change. | 1900 Note (+): Implementations are advised to not make this a special case, | 1901 but to arrange that this path rejoin the normal packet forwarding | 1902 path. All of the appropriate actions from the "On receipt of data | 1903 from S to G on interface iif" pseudocode in Section 4.2 should be | 1904 performed. 1906 KeepaliveTimer(S,G) is restarted at the RP when packets arrive on the 1907 proper tunnel interface and the RP desires to switch to the SPT or the 1908 SPTbit is already set. This may cause the upstream (S,G) state machine 1909 to trigger a join if the inherited_olist(S,G) is not NULL; 1911 An RP should preserve (S,G) state that was created in response to a 1912 Register message for at least ( 3 * Register_Suppression_Time ), 1913 otherwise the RP may stop joining (S,G) before the DR for S has 1914 restarted sending registers. Traffic would then be interrupted until 1915 the Register-Stop Timer expires at the DR. 1917 Thus, at the RP, KeepaliveTimer(S,G) should be restarted to ( 3 * 1918 Register_Suppression_Time + Register_Probe_Time ). 1920 When forwarding a packet from the Register Tunnel, the TTL of the | 1921 original data packet is decremented after it is decapsulated. 1923 The IP ECN bits should be copied from the IP header of the Register 1924 packet to the decapsulated packet. 1926 The Diffserv Code Point (DSCP) should be copied from the IP header of 1927 the Register packet to the decapsulated packet. The RP MAY retain the 1928 DSCP of the inner packet, or re-classify the packet and apply a 1929 different DSCP. Scenarios where each of these might be useful are 1930 discussed in [10]. 1932 4.5. PIM Join/Prune Messages 1934 A PIM Join/Prune message consists of a list of groups and a list of 1935 Joined and Pruned sources for each group. When processing a received 1936 Join/Prune message, each Joined or Pruned source for a Group is 1937 effectively considered individually, and applies to one or more of the 1938 following state machines. When considering a Join/Prune message whose 1939 Upstream Neighbor Address field addresses this router, (*,G) Joins and 1940 Prunes can affect both the (*,G) and (S,G,rpt) downstream state 1941 machines, while (*,*,RP), (S,G) and (S,G,rpt) Joins and Prunes can only 1942 affect their respective downstream state machines. When considering a 1943 Join/Prune message whose Upstream Neighbor Address field addresses 1944 another router, most Join or Prune messages could affect each upstream 1945 state machine. 1947 In general, a PIM Join/Prune message should only be accepted for 1948 processing if it comes from a known PIM neighbor. A PIM router hears 1949 about PIM neighbors through PIM Hello messages. If a router receives a 1950 Join/Prune message from a particular IP source address and it has not 1951 seen a PIM Hello message from that source address, then the Join/Prune 1952 message SHOULD be discarded without further processing. In addition, if 1953 the Hello message from a neighbor was authenticated using IPsec AH (see 1954 Section 6.3) then all Join/Prune messages from that neighbor MUST also 1955 be authenticated using IPsec AH. 1957 We note that some older PIM implementations incorrectly fail to send 1958 Hello messages on point-to-point interfaces, so we also RECOMMEND that a 1959 configuration option be provided to allow interoperation with such older 1960 routers, but that this configuration option SHOULD NOT be enabled by 1961 default. 1963 4.5.1. Receiving (*,*,RP) Join/Prune Messages 1965 The per-interface state machine for receiving (*,*,RP) Join/Prune 1966 Messages is given below. There are three states: 1968 NoInfo (NI) 1969 The interface has no (*,*,RP) Join state and no timers 1970 running. 1972 Join (J) 1973 The interface has (*,*,RP) Join state which will cause the 1974 router to forward packets destined for any group handled by RP 1975 from this interface except if there is also (S,G,rpt) prune 1976 information (see Section 4.5.4) or the router lost an assert 1977 on this interface. 1979 Prune-Pending (PP) 1980 The router has received a Prune(*,*,RP) on this interface from 1981 a downstream neighbor and is waiting to see whether the prune 1982 will be overridden by another downstream router. For 1983 forwarding purposes, the Prune-Pending state functions exactly 1984 like the Join state. 1986 In addition, the state machine uses two timers: 1988 ExpiryTimer (ET) 1989 This timer is restarted when a valid Join(*,*,RP) is received. 1990 Expiry of the ExpiryTimer causes the interface state to revert 1991 to NoInfo for this RP. 1993 Prune-Pending Timer (PPT) 1994 This timer is set when a valid Prune(*,*,RP) is received. 1995 Expiry of the Prune-Pending Timer causes the interface state 1996 to revert to NoInfo for this RP. 1998 Figure 2: Downstream per-interface (*,*,RP) state machine in tabular form 2000 r+-------------++----------------------------------------------------------+ 2001 | || Event | 2002 | ++-------------+--------------+--------------+--------------+ 2003 |Prev State ||Receive | Receive | Prune- | Expiry Timer | 2004 | ||Join(*,*,RP) | Prune | Pending | Expires | 2005 | || | (*,*,RP) | Timer | | 2006 | || | | Expires | | 2007 | 2008 +-------------++-------------+--------------+--------------+--------------+ 2009 | ||-> J state | -> NI state | - | - | 2010 |NoInfo (NI) ||start Expiry | | | | 2011 | ||Timer | | | | 2012 | 2013 +-------------++-------------+--------------+--------------+--------------+ 2014 | ||-> J state | -> PP state | - | -> NI state | 2015 |Join (J) ||restart | start Prune- | | | 2016 | ||Expiry Timer | Pending | | | 2017 | || | Timer | | | 2018 | 2019 +-------------++-------------+--------------+--------------+--------------+ 2020 |Prune- ||-> J state | -> PP state | -> NI state | -> NI state | 2021 |Pending (PP) ||restart | | Send Prune- | | 2022 | ||Expiry Timer | | Echo(*,*,RP) | | 2023 | 2024 +-------------++-------------+--------------+--------------+--------------+ 2026 The transition events "Receive Join(*,*,RP)" and "Receive Prune(*,*,RP)" 2027 imply receiving a Join or Prune targeted to this router's address on the 2028 received interface. If the destination address is not correct, these 2029 state transitions in this state machine must not occur, although seeing 2030 such a packet may cause state transitions in other state machines. 2032 On unnumbered interfaces on point-to-point links, the router's address | 2033 should be the same as the source address it chose for the Hello message | 2034 it sent over that interface. However on point-to-point links we also | 2035 recommend that for backwards compatibility PIM Join/Prune messages with | 2036 a destination address of all zeros are also accepted. 2038 Transitions from NoInfo State 2040 When in NoInfo state, the following event may trigger a transition: 2042 Receive Join(*,*,RP) 2043 A Join(*,*,RP) is received on interface I with its Upstream 2044 Neighbor Address set to the router's address on I. 2046 The (*,*,RP) downstream state machine on interface I 2047 transitions to the Join state. The Expiry Timer (ET) is 2048 started, and set to the HoldTime from the triggering 2049 Join/Prune message. 2051 Note that it is possible to receive a Join(*,*,RP) message for 2052 an RP that we do not have information telling us that it is an 2053 RP. In the case of (*,*,RP) state, so long as we have a route 2054 to the RP, this will not cause a problem, and the transition 2055 should still take place. 2057 Transitions from Join State 2059 When in Join state, the following events may trigger a transition: 2061 Receive Join(*,*,RP) 2062 A Join(*,*,RP) is received on interface I with its Upstream 2063 Neighbor Address set to the router's address on I. 2065 The (*,*,RP) downstream state machine on interface I remains 2066 in Join state, and the Expiry Timer (ET) is restarted, set to 2067 maximum of its current value and the HoldTime from the 2068 triggering Join/Prune message. 2070 Receive Prune(*,*,RP) 2071 A Prune(*,*,RP) is received on interface I with its Upstream 2072 Neighbor Address set to the router's address on I. 2074 The (*,*,RP) downstream state machine on interface I 2075 transitions to the Prune-Pending state. The Prune-Pending 2076 Timer is started; it is set to the J/P_Override_Interval(I) if 2077 the router has more than one neighbor on that interface; 2078 otherwise it is set to zero causing it to expire immediately. 2080 Expiry Timer Expires 2081 The Expiry Timer for the (*,*,RP) downstream state machine on 2082 interface I expires. 2084 The (*,*,RP) downstream state machine on interface I 2085 transitions to the NoInfo state. 2087 Transitions from Prune-Pending State 2089 When in Prune-Pending state, the following events may trigger a 2090 transition: 2092 Receive Join(*,*,RP) 2093 A Join(*,*,RP) is received on interface I with its Upstream 2094 Neighbor Address set to the router's address on I. 2096 The (*,*,RP) downstream state machine on interface I 2097 transitions to the Join state. The Prune-Pending Timer is 2098 canceled (without triggering an expiry event). The Expiry 2099 Timer is restarted, set to maximum of its current value and 2100 the HoldTime from the triggering Join/Prune message. 2102 Expiry Timer Expires 2103 The Expiry Timer for the (*,*,RP) downstream state machine on 2104 interface I expires. 2106 The (*,*,RP) downstream state machine on interface I 2107 transitions to the NoInfo state. 2109 Prune-Pending Timer Expires 2110 The Prune-Pending Timer for the (*,*,RP) downstream state 2111 machine on interface I expires. 2113 The (*,*,RP) downstream state machine on interface I 2114 transitions to the NoInfo state. A PruneEcho(*,*,RP) is sent 2115 onto the subnet connected to interface I. 2117 The action "Send PruneEcho(*,*,RP)" is triggered when the 2118 router stops forwarding on an interface as a result of a 2119 prune. A PruneEcho(*,*,RP) is simply a Prune(*,*,RP) message 2120 sent by the upstream router on a LAN with its own address in 2121 the Upstream Neighbor Address field. Its purpose is to add 2122 additional reliability so that if a Prune that should have 2123 been overridden by another router is lost locally on the LAN, 2124 then the PruneEcho may be received and cause the override to 2125 happen. A PruneEcho(*,*,RP) need not be sent on an interface 2126 that contains only a single PIM neighbor during the time this 2127 state machine was in Prune-Pending state. 2129 4.5.2. Receiving (*,G) Join/Prune Messages 2131 When a router receives a Join(*,G) or Prune(*,G) it must first check to 2132 see whether the RP in the message matches RP(G) (the router's idea of 2133 who the RP is). If the RP in the message does not match RP(G) the 2134 Join(*,G) or Prune(*,G) should be silently dropped. (Note that other 2135 source list entries such as (S,G,rpt) or (S,G) in the same Group 2136 Specific Set should still be processed.) If a router has no RP 2137 information (e.g. has not recently received a BSR message) then it may 2138 choose to accept Join(*,G) or Prune(*,G) and treat the RP in the message 2139 as RP(G). 2141 The per-interface state machine for receiving (*,G) Join/Prune Messages 2142 is given below. There are three states: 2144 NoInfo (NI) 2145 The interface has no (*,G) Join state and no timers running. 2147 Join (J) 2148 The interface has (*,G) Join state which will cause the router 2149 to forward packets destined for G from this interface except 2150 if there is also (S,G,rpt) prune information (see Section 2151 4.5.4) or the router lost an assert on this interface. 2153 Prune-Pending (PP) 2154 The router has received a Prune(*,G) on this interface from a 2155 downstream neighbor and is waiting to see whether the prune 2156 will be overridden by another downstream router. For 2157 forwarding purposes, the Prune-Pending state functions exactly 2158 like the Join state. 2160 In addition, the state machine uses two timers: 2162 Expiry Timer (ET) 2163 This timer is restarted when a valid Join(*,G) is received. 2164 Expiry of the Expiry Timer causes the interface state to 2165 revert to NoInfo for this group. 2167 Prune-Pending Timer (PPT) 2168 This timer is set when a valid Prune(*,G) is received. Expiry 2169 of the Prune-Pending Timer causes the interface state to 2170 revert to NoInfo for this group. 2172 Figure 3: Downstream per-interface (*,G) state machine in tabular form 2174 i+-------------++---------------------------------------------------------+ 2175 | || Event | 2176 | ++-------------+--------------+-------------+--------------+ 2177 |Prev State ||Receive | Receive | Prune- | Expiry Timer | 2178 | ||Join(*,G) | Prune(*,G) | Pending | Expires | 2179 | || | | Timer | | 2180 | || | | Expires | | 2181 | 2182 +-------------++-------------+--------------+-------------+--------------+ 2183 | ||-> J state | -> NI state | - | - | 2184 |NoInfo (NI) ||start Expiry | | | | 2185 | ||Timer | | | | 2186 | 2187 +-------------++-------------+--------------+-------------+--------------+ 2188 | ||-> J state | -> PP state | - | -> NI state | 2189 |Join (J) ||restart | start Prune- | | | 2190 | ||Expiry Timer | Pending | | | 2191 | || | Timer | | | 2192 | 2193 +-------------++-------------+--------------+-------------+--------------+ 2194 |Prune- ||-> J state | -> PP state | -> NI state | -> NI state | 2195 |Pending (PP) ||restart | | Send Prune- | | 2196 | ||Expiry Timer | | Echo(*,G) | | 2197 | 2198 +-------------++-------------+--------------+-------------+--------------+ 2200 The transition events "Receive Join(*,G)" and "Receive Prune(*,G)" imply 2201 receiving a Join or Prune targeted to this router's address on the 2202 received interface. If the destination address is not correct, these 2203 state transitions in this state machine must not occur, although seeing 2204 such a packet may cause state transitions in other state machines. 2206 On unnumbered interfaces on point-to-point links, the router's address | 2207 should be the same as the source address it chose for the Hello message | 2208 it sent over that interface. However on point-to-point links we also | 2209 recommend that for backwards compatibility PIM Join/Prune messages with | 2210 a destination address of all zeros are also accepted. 2212 Transitions from NoInfo State 2214 When in NoInfo state, the following event may trigger a transition: 2216 Receive Join(*,G) 2217 A Join(*,G) is received on interface I with its Upstream 2218 Neighbor Address set to the router's address on I. 2220 The (*,G) downstream state machine on interface I transitions 2221 to the Join state. The Expiry Timer (ET) is started, and set 2222 to the HoldTime from the triggering Join/Prune message. 2224 Transitions from Join State 2226 When in Join state, the following events may trigger a transition: 2228 Receive Join(*,G) 2229 A Join(*,G) is received on interface I with its Upstream 2230 Neighbor Address set to the router's address on I. 2232 The (*,G) downstream state machine on interface I remains in 2233 Join state, and the Expiry Timer (ET) is restarted, set to 2234 maximum of its current value and the HoldTime from the 2235 triggering Join/Prune message. 2237 Receive Prune(*,G) 2238 A Prune(*,G) is received on interface I with its Upstream 2239 Neighbor Address set to the router's address on I. 2241 The (*,G) downstream state machine on interface I transitions 2242 to the Prune-Pending state. The Prune-Pending Timer is 2243 started; it is set to the J/P_Override_Interval(I) if the 2244 router has more than one neighbor on that interface; otherwise 2245 it is set to zero causing it to expire immediately. 2247 Expiry Timer Expires 2248 The Expiry Timer for the (*,G) downstream state machine on 2249 interface I expires. 2251 The (*,G) downstream state machine on interface I transitions 2252 to the NoInfo state. 2254 Transitions from Prune-Pending State 2256 When in Prune-Pending state, the following events may trigger a 2257 transition: 2259 Receive Join(*,G) 2260 A Join(*,G) is received on interface I with its Upstream 2261 Neighbor Address set to the router's address on I. 2263 The (*,G) downstream state machine on interface I transitions 2264 to the Join state. The Prune-Pending Timer is canceled 2265 (without triggering an expiry event). The Expiry Timer is 2266 restarted, set to maximum of its current value and the 2267 HoldTime from the triggering Join/Prune message. 2269 Expiry Timer Expires 2270 The Expiry Timer for the (*,G) downstream state machine on 2271 interface I expires. 2273 The (*,G) downstream state machine on interface I transitions 2274 to the NoInfo state. 2276 Prune-Pending Timer Expires 2277 The Prune-Pending Timer for the (*,G) downstream state machine 2278 on interface I expires. 2280 The (*,G) downstream state machine on interface I transitions 2281 to the NoInfo state. A PruneEcho(*,G) is sent onto the subnet 2282 connected to interface I. 2284 The action "Send PruneEcho(*,G)" is triggered when the router 2285 stops forwarding on an interface as a result of a prune. A 2286 PruneEcho(*,G) is simply a Prune(*,G) message sent by the 2287 upstream router on a LAN with its own address in the Upstream 2288 Neighbor Address field. Its purpose is to add additional 2289 reliability so that if a Prune that should have been 2290 overridden by another router is lost locally on the LAN, then 2291 the PruneEcho may be received and cause the override to 2292 happen. A PruneEcho(*,G) need not be sent on an interface 2293 that contains only a single PIM neighbor during the time this 2294 state machine was in Prune-Pending state. 2296 4.5.3. Receiving (S,G) Join/Prune Messages 2298 The per-interface state machine for receiving (S,G) Join/Prune messages 2299 is given below, and is almost identical to that for (*,G) messages. 2300 There are three states: 2302 NoInfo (NI) 2303 The interface has no (S,G) Join state and no (S,G) timers 2304 running. 2306 Join (J) 2307 The interface has (S,G) Join state which will cause the router 2308 to forward packets from S destined for G from this interface 2309 if the (S,G) state is active (the SPTbit is set) except if the 2310 router lost an assert on this interface. 2312 Prune-Pending (PP) 2313 The router has received a Prune(S,G) on this interface from a 2314 downstream neighbor and is waiting to see whether the prune 2315 will be overridden by another downstream router. For 2316 forwarding purposes, the Prune-Pending state functions exactly 2317 like the Join state. 2319 In addition, there are two timers: 2321 Expiry Timer (ET) 2322 This timer is set when a valid Join(S,G) is received. Expiry 2323 of the Expiry Timer causes this state machine to revert to 2324 NoInfo state. 2326 Prune-Pending Timer (PPT) 2327 This timer is set when a valid Prune(S,G) is received. Expiry 2328 of the Prune-Pending Timer causes this state machine to revert 2329 to NoInfo state. 2331 Figure 4: Downstream per-interface (S,G) state machine in tabular form 2333 i+-------------++---------------------------------------------------------+ 2334 | || Event | 2335 | ++-------------+--------------+-------------+--------------+ 2336 |Prev State ||Receive | Receive | Prune- | Expiry Timer | 2337 | ||Join(S,G) | Prune(S,G) | Pending | Expires | 2338 | || | | Timer | | 2339 | || | | Expires | | 2340 | 2341 +-------------++-------------+--------------+-------------+--------------+ 2342 | ||-> J state | -> NI state | - | - | 2343 |NoInfo (NI) ||start Expiry | | | | 2344 | ||Timer | | | | 2345 | 2346 +-------------++-------------+--------------+-------------+--------------+ 2347 | ||-> J state | -> PP state | - | -> NI state | 2348 |Join (J) ||restart | start Prune- | | | 2349 | ||Expiry Timer | Pending | | | 2350 | || | Timer | | | 2351 | 2352 +-------------++-------------+--------------+-------------+--------------+ 2353 |Prune- ||-> J state | -> PP state | -> NI state | -> NI state | 2354 |Pending (PP) ||restart | | Send Prune- | | 2355 | ||Expiry Timer | | Echo(S,G) | | 2356 | 2357 +-------------++-------------+--------------+-------------+--------------+ 2359 The transition events "Receive Join(S,G)" and "Receive Prune(S,G)" imply 2360 receiving a Join or Prune targeted to this router's address on the 2361 received interface. If the destination address is not correct, these 2362 state transitions in this state machine must not occur, although seeing 2363 such a packet may cause state transitions in other state machines. 2365 On unnumbered interfaces on point-to-point links, the router's address | 2366 should be the same as the source address it chose for the Hello message | 2367 it sent over that interface. However on point-to-point links we also | 2368 recommend that for backwards compatibility PIM Join/Prune messages with | 2369 a destination address of all zeros are also accepted. 2371 Transitions from NoInfo State 2373 When in NoInfo state, the following event may trigger a transition: 2375 Receive Join(S,G) 2376 A Join(S,G) is received on interface I with its Upstream 2377 Neighbor Address set to the router's address on I. 2379 The (S,G) downstream state machine on interface I transitions 2380 to the Join state. The Expiry Timer (ET) is started, and set 2381 to the HoldTime from the triggering Join/Prune message. 2383 Transitions from Join State 2385 When in Join state, the following events may trigger a transition: 2387 Receive Join(S,G) 2388 A Join(S,G) is received on interface I with its Upstream 2389 Neighbor Address set to the router's address on I. 2391 The (S,G) downstream state machine on interface I remains in 2392 Join state, and the Expiry Timer (ET) is restarted, set to 2393 maximum of its current value and the HoldTime from the 2394 triggering Join/Prune message. 2396 Receive Prune(S,G) 2397 A Prune(S,G) is received on interface I with its Upstream 2398 Neighbor Address set to the router's address on I. 2400 The (S,G) downstream state machine on interface I transitions 2401 to the Prune-Pending state. The Prune-Pending Timer is 2402 started; it is set to the J/P_Override_Interval(I) if the 2403 router has more than one neighbor on that interface; otherwise 2404 it is set to zero causing it to expire immediately. 2406 Expiry Timer Expires 2407 The Expiry Timer for the (S,G) downstream state machine on 2408 interface I expires. 2410 The (S,G) downstream state machine on interface I transitions 2411 to the NoInfo state. 2413 Transitions from Prune-Pending State 2415 When in Prune-Pending state, the following events may trigger a 2416 transition: 2418 Receive Join(S,G) 2419 A Join(S,G) is received on interface I with its Upstream 2420 Neighbor Address set to the router's address on I. 2422 The (S,G) downstream state machine on interface I transitions 2423 to the Join state. The Prune-Pending Timer is canceled 2424 (without triggering an expiry event). The Expiry Timer is 2425 restarted, set to maximum of its current value and the 2426 HoldTime from the triggering Join/Prune message. 2428 Expiry Timer Expires 2429 The Expiry Timer for the (S,G) downstream state machine on 2430 interface I expires. 2432 The (S,G) downstream state machine on interface I transitions 2433 to the NoInfo state. 2435 Prune-Pending Timer Expires 2436 The Prune-Pending Timer for the (S,G) downstream state machine 2437 on interface I expires. 2439 The (S,G) downstream state machine on interface I transitions 2440 to the NoInfo state. A PruneEcho(S,G) is sent onto the subnet 2441 connected to interface I. 2443 The action "Send PruneEcho(S,G)" is triggered when the router 2444 stops forwarding on an interface as a result of a prune. A 2445 PruneEcho(S,G) is simply a Prune(S,G) message sent by the 2446 upstream router on a LAN with its own address in the Upstream 2447 Neighbor Address field. Its purpose is to add additional 2448 reliability so that if a Prune that should have been 2449 overridden by another router is lost locally on the LAN, then 2450 the PruneEcho may be received and cause the override to 2451 happen. A PruneEcho(S,G) need not be sent on an interface 2452 that contains only a single PIM neighbor during the time this 2453 state machine was in Prune-Pending state. 2455 4.5.4. Receiving (S,G,rpt) Join/Prune Messages 2457 The per-interface state machine for receiving (S,G,rpt) Join/Prune 2458 messages is given below. There are five states: 2460 NoInfo (NI) 2461 The interface has no (S,G,rpt) Prune state and no (S,G,rpt) 2462 timers running. 2464 Prune (P) 2465 The interface has (S,G,rpt) Prune state which will cause the 2466 router not to forward packets from S destined for G from this 2467 interface even though the interface has active (*,G) Join 2468 state. 2470 Prune-Pending (PP) 2471 The router has received a Prune(S,G,rpt) on this interface 2472 from a downstream neighbor and is waiting to see whether the 2473 prune will be overridden by another downstream router. For 2474 forwarding purposes, the Prune-Pending state functions exactly 2475 like the NoInfo state. 2477 PruneTmp (P') 2478 This state is a transient state which for forwarding purposes 2479 behaves exactly like the Prune state. A (*,G) Join has been 2480 received (which may cancel the (S,G,rpt) Prune). As we parse 2481 the Join/Prune message from top to bottom, we first enter this 2482 state if the message contains a (*,G) Join. Later in the 2483 message we will normally encounter an (S,G,rpt) prune to re- 2484 instate the Prune state. However if we reach the end of the 2485 message without encountering such a (S,G,rpt) prune, then we 2486 will revert to NoInfo state in this state machine. 2488 As no time is spent in this state, no timers can expire. 2490 Prune-Pending-Tmp (PP') 2491 This state is a transient state which is identical to P' 2492 except that it is associated with the PP state rather than the 2493 P state. For forwarding purposes, PP' behaves exactly like PP 2494 state. 2496 In addition, there are two timers: 2498 Expiry Timer (ET) 2499 This timer is set when a valid Prune(S,G,rpt) is received. 2500 Expiry of the Expiry Timer causes this state machine to revert 2501 to NoInfo state. 2503 Prune-Pending Timer (PPT) 2504 This timer is set when a valid Prune(S,G,rpt) is received. 2505 Expiry of the Prune-Pending Timer causes this state machine to 2506 move on to Prune state. 2508 Figure 5: Downstream per-interface (S,G,rpt) state machine in tabular form 2510 r+----------++----------------------------------------------------------------+ 2511 | || Event | 2512 | ++----------+-----------+-----------+---------+---------+---------+ 2513 |Prev ||Receive | Receive | Receive | End of | Prune- | Expiry | 2514 |State ||Join(*,G) | Join | Prune | Message | Pending | Timer | 2515 | || | (S,G,rpt) | (S,G,rpt) | | Timer | Expires | 2516 | || | | | | Expires | | 2517 +----------++----------+-----------+-----------+---------+---------+---------+ 2518 | ||- | - | -> PP | - | - | - | 2519 | || | | state | | | | 2520 | || | | start | | | | 2521 |NoInfo || | | Prune- | | | | 2522 |(NI) || | | Pending | | | | 2523 | || | | Timer; | | | | 2524 | || | | start | | | | 2525 | || | | Expiry | | | | 2526 | || | | Timer | | | | 2527 +----------++----------+-----------+-----------+---------+---------+---------+ 2528 | ||-> P' | -> NI | -> P | - | - | -> NI | 2529 | ||state | state | state | | | state | 2530 |Prune (P) || | | restart | | | | 2531 | || | | Expiry | | | | 2532 | || | | Timer | | | | 2533 +----------++----------+-----------+-----------+---------+---------+---------+ 2534 |Prune- ||-> PP' | -> NI | - | - | -> P | - | 2535 |Pending ||state | state | | | state | | 2536 |(PP) || | | | | | | 2537 +----------++----------+-----------+-----------+---------+---------+---------+ 2538 | ||- | - | -> P | -> NI | - | - | 2539 |Prune-Tmp || | | state | state | | | 2540 |(P') || | | restart | | | | 2541 | || | | Expiry | | | | 2542 | || | | Timer | | | | 2543 +----------++----------+-----------+-----------+---------+---------+---------+ 2544 | ||- | - | -> PP | -> NI | - | - | 2545 |Prune- || | | state | state | | | 2546 |Pending- || | | restart | | | | 2547 |Tmp (PP') || | | Expiry | | | | 2548 | || | | Timer | | | | 2549 +----------++----------+-----------+-----------+---------+---------+---------+ 2551 The transition events "Receive Join(S,G,rpt)", "Receive Prune(S,G,rpt)", 2552 and "Receive Join(*,G)" imply receiving a Join or Prune targeted to this 2553 router's address on the received interface. If the destination address 2554 is not correct, these state transitions in this state machine must not 2555 occur, although seeing such a packet may cause state transitions in 2556 other state machines. 2558 On unnumbered interfaces on point-to-point links, the router's address 2559 should be the same as the source address it chose for the Hello message 2560 it sent over that interface. However on point-to-point links we also 2561 recommend that PIM Join/Prune messages with a destination address of all 2562 zeros are also accepted. 2564 Transitions from NoInfo State 2566 When in NoInfo (NI) state, the following event may trigger a transition: 2568 Receive Prune(S,G,rpt) 2569 A Prune(S,G,rpt) is received on interface I with its Upstream 2570 Neighbor Address set to the router's address on I. 2572 The (S,G,rpt) downstream state machine on interface I 2573 transitions to the Prune-Pending state. The Expiry Timer (ET) 2574 is started, and set to the HoldTime from the triggering 2575 Join/Prune message. The Prune-Pending Timer is started; it is 2576 set to the J/P_Override_Interval(I) if the router has more 2577 than one neighbor on that interface; otherwise it is set to 2578 zero causing it to expire immediately. 2580 Transitions from Prune-Pending State 2582 When in Prune-Pending (PP) state, the following events may trigger a 2583 transition: 2585 Receive Join(*,G) 2586 A Join(*,G) is received on interface I with its Upstream 2587 Neighbor Address set to the router's address on I. 2589 The (S,G,rpt) downstream state machine on interface I 2590 transitions to Prune-Pending-Tmp state whilst the remainder of 2591 the compound Join/Prune message containing the Join(*,G) is 2592 processed. 2594 Receive Join(S,G,rpt) 2595 A Join(S,G,rpt) is received on interface I with its Upstream 2596 Neighbor Address set to the router's address on I. 2598 The (S,G,rpt) downstream state machine on interface I 2599 transitions to NoInfo state. ET and PPT are canceled. 2601 Prune-Pending Timer Expires 2602 The Prune-Pending Timer for the (S,G,rpt) downstream state 2603 machine on interface I expires. 2605 The (S,G,rpt) downstream state machine on interface I 2606 transitions to the Prune state. 2608 Transitions from Prune State 2610 When in Prune (P) state, the following events may trigger a transition: 2612 Receive Join(*,G) 2613 A Join(*,G) is received on interface I with its Upstream 2614 Neighbor Address set to the router's address on I. 2616 The (S,G,rpt) downstream state machine on interface I 2617 transitions to PruneTmp state whilst the remainder of the 2618 compound Join/Prune message containing the Join(*,G) is 2619 processed. 2621 Receive Join(S,G,rpt) 2622 A Join(S,G,rpt) is received on interface I with its Upstream 2623 Neighbor Address set to the router's address on I. 2625 The (S,G,rpt) downstream state machine on interface I 2626 transitions to NoInfo state. ET and PPT are canceled. 2628 Receive Prune(S,G,rpt) 2629 A Prune(S,G,rpt) is received on interface I with its Upstream 2630 Neighbor Address set to the router's address on I. 2632 The (S,G,rpt) downstream state machine on interface I remains 2633 in Prune state. The Expiry Timer (ET) is restarted, set to 2634 maximum of its current value and the HoldTime from the 2635 triggering Join/Prune message. 2637 Expiry Timer Expires 2638 The Expiry Timer for the (S,G,rpt) downstream state machine on 2639 interface I expires. 2641 The (S,G,rpt) downstream state machine on interface I 2642 transitions to the NoInfo state. 2644 Transitions from Prune-Pending-Tmp State 2646 When in Prune-Pending-Tmp (PP') state and processing a compound 2647 Join/Prune message, the following events may trigger a transition: 2649 Receive Prune(S,G,rpt) 2650 The compound Join/Prune message contains a Prune(S,G,rpt). 2652 The (S,G,rpt) downstream state machine on interface I 2653 transitions back to the Prune-Pending state. The Expiry Timer 2654 (ET) is restarted, set to maximum of its current value and the 2655 HoldTime from the triggering Join/Prune message. 2657 End of Message 2658 The end of the compound Join/Prune message is reached. 2660 The (S,G,rpt) downstream state machine on interface I 2661 transitions to the NoInfo state. ET and PPT are canceled. 2663 Transitions from PruneTmp State 2665 When in PruneTmp (P') state and processing a compound Join/Prune 2666 message, the following events may trigger a transition: 2668 Receive Prune(S,G,rpt) 2669 The compound Join/Prune message contains a Prune(S,G,rpt). 2671 The (S,G,rpt) downstream state machine on interface I 2672 transitions back to the Prune state. The Expiry Timer (ET) is 2673 restarted, set to maximum of its current value and the 2674 HoldTime from the triggering Join/Prune message. 2676 End of Message 2677 The end of the compound Join/Prune message is reached. 2679 The (S,G,rpt) downstream state machine on interface I 2680 transitions to the NoInfo state. ET is canceled. 2682 Notes: 2684 Receiving a Prune(*,G) does not affect the (S,G,rpt) downstream state 2685 machine. 2687 Receiving a Join(*,*,RP) does not affect the (S,G,rpt) downstream state 2688 machine. If a router has originated Join(*,*,RP) and pruned a source 2689 off it using Prune(S,G,rpt), then to receive that source again it should 2690 explicitly re-join using Join(S,G,rpt) or Join(*,G). In some LAN 2691 topologies it is possible for a router sending a new Join(*,*,RP) to 2692 have to wait as much as a Join/Prune Interval before noticing that it 2693 needs to override a neighbor's pre-existing Prune(S,G,rpt). This is 2694 considered acceptable, as (*,*,RP) state is intended to be used only in 2695 long-lived and persistent scenarios. 2697 4.5.5. Sending (*,*,RP) Join/Prune Messages 2699 The per-interface state machines for (*,*,RP) hold join state from 2700 downstream PIM routers. This state then determines whether a router 2701 needs to propagate a Join(*,*,RP) upstream towards the RP. 2703 If a router wishes to propagate a Join(*,*,RP) upstream, it must also 2704 watch for messages on its upstream interface from other routers on that 2705 subnet, and these may modify its behavior. If it sees a Join(*,*,RP) to 2706 the correct upstream neighbor, it should suppress its own Join(*,*,RP). 2707 If it sees a Prune(*,*,RP) to the correct upstream neighbor, it should 2708 be prepared to override that prune by sending a Join(*,*,RP) almost 2709 immediately. Finally, if it sees the Generation ID (see Section 4.3) of 2710 the correct upstream neighbor change, it knows that the upstream 2711 neighbor has lost state, and it should be prepared to refresh the state 2712 by sending a Join(*,*,RP) almost immediately. 2714 In addition, if the MRIB changes to indicate that the next hop towards 2715 the RP has changed, the router should prune off from the old next hop, 2716 and join towards the new next hop. 2718 The upstream (*,*,RP) state machine contains only two states: 2720 Not Joined 2721 The downstream state machines and local membership information do 2722 not indicate that the router needs to join the (*,*,RP) tree for 2723 this RP. 2725 Joined 2726 The downstream state machines and local membership information 2727 indicate that the router should join the (*,*,RP) tree for this RP. 2729 In addition, one timer JT(*,*,RP) is kept which is used to trigger the 2730 sending of a Join(*,*,RP) to the upstream next hop towards the RP, 2731 NBR(RPF_interface(RP), MRIB.next_hop(RP)). 2733 Figure 6: Upstream (*,*,RP) state machine in tabular form 2735 +--------------------++-------------------------------------------------+ 2736 | || Event | 2737 | Prev State ++-------------------------+-----------------------+ 2738 | || JoinDesired | JoinDesired | 2739 | || (*,*,RP) ->True | (*,*,RP) ->False | 2740 | 2741 +--------------------++-------------------------+-----------------------+ 2742 | || -> J state | - | 2743 | NotJoined (NJ) || Send Join(*,*,RP); | | 2744 | || Set Join Timer to | | 2745 | || t_periodic | | 2746 | 2747 +--------------------++-------------------------+-----------------------+ 2748 | Joined (J) || - | -> NJ state | 2749 | || | Send Prune | 2750 | || | (*,*,RP); Cancel | 2751 | || | Join Timer | 2752 | 2753 +--------------------++-------------------------+-----------------------+ 2755 In addition, we have the following transitions which occur within the 2756 Joined state: 2758 i+-----------------------------------------------------------------------+ 2759 | In Joined (J) State | 2760 | 2761 +-------------------+--------------------+------------------------------+ 2762 | Timer Expires | See | See | 2763 | | Join(*,*,RP) | Prune(*,*,RP) | 2764 | | to MRIB. | to MRIB. | 2765 | | next_hop(RP) | next_hop(RP) | 2766 | 2767 +-------------------+--------------------+------------------------------+ 2768 | Send | Increase Join | Decrease Join | 2769 | Join(*,*,RP); | Timer to | Timer to | 2770 | Set Join Timer | t_joinsuppress | t_override | 2771 | to t_periodic | | | 2772 | 2773 +-------------------+--------------------+------------------------------+ 2774 T+-----------------------------------------------------------------------+ 2775 | In Joined (J) State | 2776 | 2777 +-----------------------------------+-----------------------------------+ 2778 | NBR(RPF_interface(RP), | MRIB.next_hop(RP) GenID | 2779 | MRIB.next_hop(RP)) | changes | 2780 | changes | | 2781 | 2782 +-----------------------------------+-----------------------------------+ 2783 | Send Join(*,*,RP) to new | Decrease Join Timer to | 2784 | next hop; Send | t_override | 2785 | Prune(*,*,RP) to old | | 2786 | next hop; set Join Timer | | 2787 | to t_periodic | | 2788 | 2789 +-----------------------------------+-----------------------------------+ 2791 This state machine uses the following macro: 2793 bool JoinDesired(*,*,RP) { 2794 if immediate_olist(*,*,RP) != NULL 2795 return TRUE 2796 else 2797 return FALSE 2798 } 2800 JoinDesired(*,*,RP) is true when the router has received (*,*,RP) Joins 2801 from any downstream interface. Note that although JoinDesired is true, 2802 the router's sending of a Join(*,*,RP) message may be suppressed by 2803 another router sending a Join(*,*,RP) onto the upstream interface. 2805 Transitions from NotJoined State 2807 When the upstream (*,*,RP) state machine is in NotJoined state, the 2808 following event may trigger a state transition: 2810 JoinDesired(*,*,RP) becomes True 2811 The downstream state for (*,*,RP) has changed so that at least 2812 one interface is in immediate_olist(*,*,RP), making 2813 JoinDesired(*,*,RP) become True. 2815 The upstream (*,*,RP) state machine transitions to Joined 2816 state. Send Join(*,*,RP) to the appropriate upstream 2817 neighbor, which is NBR(RPF_interface(RP), MRIB.next_hop(RP)). 2818 Set the Join Timer (JT) to expire after t_periodic seconds. 2820 Transitions from Joined State 2822 When the upstream (*,*,RP) state machine is in Joined state, the 2823 following events may trigger state transitions: 2825 JoinDesired(*,*,RP) becomes False 2826 The downstream state for (*,*,RP) has changed so no interface 2827 is in immediate_olist(*,*,RP), making JoinDesired(*,*,RP) 2828 become False. 2830 The upstream (*,*,RP) state machine transitions to NotJoined 2831 state. Send Prune(*,*,RP) to the appropriate upstream 2832 neighbor, which is NBR(RPF_interface(RP), MRIB.next_hop(RP)). 2833 Cancel the Join Timer (JT). 2835 Join Timer Expires 2836 The Join Timer (JT) expires, indicating time to send a 2837 Join(*,*,RP) 2839 Send Join(*,*,RP) to the appropriate upstream neighbor, which 2840 is NBR(RPF_interface(RP), MRIB.next_hop(RP)). Restart the 2841 Join Timer (JT) to expire after t_periodic seconds. 2843 See Join(*,*,RP) to MRIB.next_hop(RP) 2844 This event is only relevant if RPF_interface(RP) is a shared 2845 medium. This router sees another router on RPF_interface(RP) 2846 send a Join(*,*,RP) to any of the addresses belonging to 2847 NBR(RPF_interface(RP), MRIB.next_hop(RP)). This causes this 2848 router to suppress its own Join. 2850 The upstream (*,*,RP) state machine remains in Joined state. 2852 Let t_joinsuppress be the minimum of t_suppressed and the 2853 HoldTime from the Join/Prune message triggering this event. 2854 If the Join Timer is set to expire in less than t_joinsuppress 2855 seconds, reset it so that it expires after t_joinsuppress 2856 seconds. If the Join Timer is set to expire in more than 2857 t_joinsuppress seconds, leave it unchanged. 2859 See Prune(*,*,RP) to MRIB.next_hop(RP) 2860 This event is only relevant if RPF_interface(RP) is a shared 2861 medium. This router sees another router on RPF_interface(RP) 2862 send a Prune(*,*,RP) to any of the addresses belonging to 2863 NBR(RPF_interface(RP), MRIB.next_hop(RP)). As this router is 2864 in Joined state, it must override the Prune after a short 2865 random interval. 2867 The upstream (*,*,RP) state machine remains in Joined state. 2868 If the Join Timer is set to expire in more than t_override 2869 seconds, reset it so that it expires after t_override seconds. 2870 If the Join Timer is set to expire in less than t_override 2871 seconds, leave it unchanged. 2873 NBR(RPF_interface(RP), MRIB.next_hop(RP)) changes 2874 A change in the MRIB routing base causes the next hop towards 2875 the RP to change. 2877 The upstream (*,*,RP) state machine remains in Joined state. 2878 Send Join(*,*,RP) to the new upstream neighbor which is the 2879 new value of NBR(RPF_interface(RP), MRIB.next_hop(RP)). Send 2880 Prune(*,*,RP) to the old upstream neighbor, which is the old 2881 value of NBR(RPF_interface(RP), MRIB.next_hop(RP)). Set the 2882 Join Timer (JT) to expire after t_periodic seconds. 2884 MRIB.next_hop(RP) GenID changes 2885 The Generation ID of the router that is MRIB.next_hop(RP) 2886 changes. This normally means that this neighbor has lost 2887 state, and so the state must be refreshed. 2889 The upstream (*,*,RP) state machine remains in Joined state. 2890 If the Join Timer is set to expire in more than t_override 2891 seconds, reset it so that it expires after t_override seconds. 2893 4.5.6. Sending (*,G) Join/Prune Messages 2895 The per-interface state machines for (*,G) hold join state from 2896 downstream PIM routers. This state then determines whether a router 2897 needs to propagate a Join(*,G) upstream towards the RP. 2899 If a router wishes to propagate a Join(*,G) upstream, it must also watch 2900 for messages on its upstream interface from other routers on that 2901 subnet, and these may modify its behavior. If it sees a Join(*,G) to 2902 the correct upstream neighbor, it should suppress its own Join(*,G). If 2903 it sees a Prune(*,G) to the correct upstream neighbor, it should be 2904 prepared to override that prune by sending a Join(*,G) almost 2905 immediately. Finally, if it sees the Generation ID (see Section 4.3) of 2906 the correct upstream neighbor change, it knows that the upstream 2907 neighbor has lost state, and it should be prepared to refresh the state 2908 by sending a Join(*,G) almost immediately. 2910 If a (*,G) Assert occurs on the upstream interface, and this changes 2911 this router's idea of the upstream neighbor, it should be prepared to 2912 ensure that the Assert winner is aware of downstream routers by sending 2913 a Join(*,G) almost immediately. 2915 In addition, if the MRIB changes to indicate that the next hop towards 2916 the RP has changed, and either the upstream interface changes or there 2917 is no Assert winner on the upstream interface, the router should prune 2918 off from the old next hop, and join towards the new next hop. 2920 The upstream (*,G) state machine only contains two states: 2922 Not Joined 2923 The downstream state machines indicate that the router does not 2924 need to join the RP tree for this group. 2926 Joined 2927 The downstream state machines indicate that the router should join 2928 the RP tree for this group. 2930 In addition, one timer JT(*,G) is kept which is used to trigger the 2931 sending of a Join(*,G) to the upstream next hop towards the RP, 2932 RPF'(*,G). 2934 Figure 7: Upstream (*,G) state machine in tabular form 2936 +--------------------++-------------------------------------------------+ 2937 | || Event | 2938 | Prev State ++------------------------+------------------------+ 2939 | || JoinDesired(*,G) | JoinDesired(*,G) | 2940 | || ->True | ->False | 2941 | 2942 +--------------------++------------------------+------------------------+ 2943 | || -> J state | - | 2944 | NotJoined (NJ) || Send Join(*,G); | | 2945 | || Set Join Timer to | | 2946 | || t_periodic | | 2947 | 2948 +--------------------++------------------------+------------------------+ 2949 | Joined (J) || - | -> NJ state | 2950 | || | Send Prune(*,G); | 2951 | || | Cancel Join Timer | 2952 | 2953 +--------------------++------------------------+------------------------+ 2955 In addition, we have the following transitions which occur within the 2956 Joined state: 2958 i+-----------------------------------------------------------------------+ 2959 | In Joined (J) State | 2960 | 2961 +-----------------+-----------------+-----------------+-----------------+ 2962 |Timer Expires | See Join(*,G) | See Prune(*,G) | RPF'(*,G) | 2963 | | to RPF'(*,G) | to RPF'(*,G) | changes due to | 2964 | | | | an Assert | 2965 | 2966 +-----------------+-----------------+-----------------+-----------------+ 2967 |Send | Increase Join | Decrease Join | Decrease Join | 2968 |Join(*,G); Set | Timer to | Timer to | Timer to | 2969 |Join Timer to | t_joinsuppress | t_override | t_override | 2970 |t_periodic | | | | 2971 | 2972 +-----------------+-----------------+-----------------+-----------------+ 2974 -+-----------------------------------------------------------------------+ 2975 | In Joined (J) State | 2976 | 2977 +----------------------------------+------------------------------------+ 2978 | RPF'(*,G) changes not | RPF'(*,G) GenID changes | 2979 | due to an Assert | | 2980 | 2981 +----------------------------------+------------------------------------+ 2982 | Send Join(*,G) to new | Decrease Join Timer to | 2983 | next hop; Send | t_override | 2984 | Prune(*,G) to old next | | 2985 | hop; Set Join Timer to | | 2986 | t_periodic | | 2987 | 2988 +----------------------------------+------------------------------------+ 2989 This state machine uses the following macro: 2991 bool JoinDesired(*,G) { 2992 if (immediate_olist(*,G) != NULL OR 2993 (JoinDesired(*,*,RP(G)) AND 2994 AssertWinner(*, G, RPF_interface(RP(G))) != NULL)) 2995 return TRUE 2996 else 2997 return FALSE 2998 } 3000 JoinDesired(*,G) is true when the router has forwarding state that would 3001 cause it to forward traffic for G using shared tree state. Note that 3002 although JoinDesired is true, the router's sending of a Join(*,G) 3003 message may be suppressed by another router sending a Join(*,G) onto the 3004 upstream interface. 3006 Transitions from NotJoined State 3008 When the upstream (*,G) state machine is in NotJoined state, the 3009 following event may trigger a state transition: 3011 JoinDesired(*,G) becomes True 3012 The macro JoinDesired(*,G) becomes True, e.g., because the | 3013 downstream state for (*,G) has changed so that at least one | 3014 interface is in immediate_olist(*,G). 3016 The upstream (*,G) state machine transitions to Joined state. 3017 Send Join(*,G) to the appropriate upstream neighbor, which is 3018 RPF'(*,G). Set the Join Timer (JT) to expire after t_periodic 3019 seconds. 3021 Transitions from Joined State 3023 When the upstream (*,G) state machine is in Joined state, the following 3024 events may trigger state transitions: 3026 JoinDesired(*,G) becomes False 3027 The macro JoinDesired(*,G) becomes False, e.g., because the | 3028 downstream state for (*,G) has changed so no interface is in | 3029 immediate_olist(*,G). 3031 The upstream (*,G) state machine transitions to NotJoined 3032 state. Send Prune(*,G) to the appropriate upstream neighbor, 3033 which is RPF'(*,G). Cancel the Join Timer (JT). 3035 Join Timer Expires 3036 The Join Timer (JT) expires, indicating time to send a 3037 Join(*,G) 3039 Send Join(*,G) to the appropriate upstream neighbor, which is 3040 RPF'(*,G). Restart the Join Timer (JT) to expire after 3041 t_periodic seconds. 3043 See Join(*,G) to RPF'(*,G) 3044 This event is only relevant if RPF_interface(RP(G)) is a 3045 shared medium. This router sees another router on 3046 RPF_interface(RP(G)) send a Join(*,G) to RPF'(*,G). This 3047 causes this router to suppress its own Join. 3049 The upstream (*,G) state machine remains in Joined state. 3051 Let t_joinsuppress be the minimum of t_suppressed and the 3052 HoldTime from the Join/Prune message triggering this event. 3053 If the Join Timer is set to expire in less than t_joinsuppress 3054 seconds, reset it so that it expires after t_joinsuppress 3055 seconds. If the Join Timer is set to expire in more than 3056 t_joinsuppress seconds, leave it unchanged. 3058 See Prune(*,G) to RPF'(*,G) 3059 This event is only relevant if RPF_interface(RP(G)) is a 3060 shared medium. This router sees another router on 3061 RPF_interface(RP(G)) send a Prune(*,G) to RPF'(*,G). As this 3062 router is in Joined state, it must override the Prune after a 3063 short random interval. 3065 The upstream (*,G) state machine remains in Joined state. If 3066 the Join Timer is set to expire in more than t_override 3067 seconds, reset it so that it expires after t_override seconds. 3068 If the Join Timer is set to expire in less than t_override 3069 seconds, leave it unchanged. 3071 RPF'(*,G) changes due to an Assert 3072 The current next hop towards the RP changes due to an 3073 Assert(*,G) on the RPF_interface(RP(G)). 3075 The upstream (*,G) state machine remains in Joined state. If 3076 the Join Timer is set to expire in more than t_override 3077 seconds, reset it so that it expires after t_override seconds. 3078 If the Join Timer is set to expire in less than t_override 3079 seconds, leave it unchanged. 3081 RPF'(*,G) changes not due to an Assert 3082 An event occurred which caused the next hop towards the RP for 3083 G to change. This may be caused by a change in the MRIB 3084 routing database or the group-to-RP mapping. Note that this 3085 transition does not occur if an Assert is active and the 3086 upstream interface does not change. 3088 The upstream (*,G) state machine remains in Joined state. 3089 Send Join(*,G) to the new upstream neighbor which is the new 3090 value of RPF'(*,G). Send Prune(*,G) to the old upstream 3091 neighbor, which is the old value of RPF'(*,G). Set the Join 3092 Timer (JT) to expire after t_periodic seconds. 3094 RPF'(*,G) GenID changes 3095 The Generation ID of the router that is RPF'(*,G) changes. 3096 This normally means that this neighbor has lost state, and so 3097 the state must be refreshed. 3099 The upstream (*,G) state machine remains in Joined state. If 3100 the Join Timer is set to expire in more than t_override 3101 seconds, reset it so that it expires after t_override seconds. 3103 4.5.7. Sending (S,G) Join/Prune Messages 3105 The per-interface state machines for (S,G) hold join state from 3106 downstream PIM routers. This state then determines whether a router 3107 needs to propagate a Join(S,G) upstream towards the source. 3109 If a router wishes to propagate a Join(S,G) upstream, it must also watch 3110 for messages on its upstream interface from other routers on that 3111 subnet, and these may modify its behavior. If it sees a Join(S,G) to 3112 the correct upstream neighbor, it should suppress its own Join(S,G). If 3113 it sees a Prune(S,G), Prune(S,G,rpt), or Prune(*,G) to the correct 3114 upstream neighbor towards S, it should be prepared to override that 3115 prune by scheduling a Join(S,G) to be sent almost immediately. Finally, 3116 if it sees the Generation ID of its upstream neighbor change, it knows 3117 that the upstream neighbor has lost state, and it should refresh the 3118 state by scheduling a Join(S,G) to be sent almost immediately. 3120 If a (S,G) Assert occurs on the upstream interface, and this changes the 3121 this router's idea of the upstream neighbor, it should be prepared to 3122 ensure that the Assert winner is aware of downstream routers by 3123 scheduling a Join(S,G) to be sent almost immediately. 3125 In addition, if MRIB changes cause the next hop towards the source to 3126 change, and either the upstream interface changes or there is no Assert 3127 winner on the upstream interface, the router should send a prune to the 3128 old next hop, and a join to the new next hop. 3130 The upstream (S,G) state machine only contains two states: 3132 Not Joined 3133 The downstream state machines and local membership information do 3134 not indicate that the router needs to join the shortest-path tree 3135 for this (S,G). 3137 Joined 3138 The downstream state machines and local membership information 3139 indicate that the router should join the shortest-path tree for 3140 this (S,G). 3142 In addition, one timer JT(S,G) is kept which is used to trigger the 3143 sending of a Join(S,G) to the upstream next hop towards S, RPF'(S,G). 3145 Figure 8: Upstream (S,G) state machine in tabular form 3147 +--------------------+--------------------------------------------------+ 3148 | | Event | 3149 | Prev State +-------------------------+------------------------+ 3150 | | JoinDesired(S,G) | JoinDesired(S,G) | 3151 | | ->True | ->False | 3152 | 3153 +--------------------+-------------------------+------------------------+ 3154 | NotJoined (NJ) | -> J state | - | 3155 | | Send Join(S,G); | | 3156 | | Set Join Timer to | | 3157 | | t_periodic | | 3158 | 3159 +--------------------+-------------------------+------------------------+ 3160 | Joined (J) | - | -> NJ state | 3161 | | | Send Prune(S,G); | 3162 | | | Set SPTbit(S,G) to | 3163 | | | FALSE; Cancel Join | 3164 | | | Timer | 3165 | 3166 +--------------------+-------------------------+------------------------+ 3167 In addition, we have the following transitions which occur within the 3168 Joined state: 3170 i+-----------------------------------------------------------------------+ 3171 | In Joined (J) State | 3172 | 3173 +-----------------+-----------------+------------------+----------------+ 3174 | Timer Expires | See Join(S,G) | See Prune(S,G) | See Prune | 3175 | | to RPF'(S,G) | to RPF'(S,G) | (S,G,rpt) to | 3176 | | | | RPF'(S,G) | 3177 | 3178 +-----------------+-----------------+------------------+----------------+ 3179 | Send | Increase Join | Decrease Join | Decrease Join | 3180 | Join(S,G); Set | Timer to | Timer to | Timer to | 3181 | Join Timer to | t_joinsuppress | t_override | t_override | 3182 | t_periodic | | | | 3183 | 3184 +-----------------+-----------------+------------------+----------------+ 3186 -+-----------------------------------------------------------------------+ 3187 | In Joined (J) State | 3188 | 3189 +-----------------+-----------------+-----------------+-----------------+ 3190 | See Prune(*,G) | RPF'(S,G) | RPF'(S,G) | RPF'(S,G) | 3191 | to RPF'(S,G) | changes not | GenID changes | changes due to | 3192 | | due to an | | an Assert | 3193 | | Assert | | | 3194 | 3195 +-----------------+-----------------+-----------------+-----------------+ 3196 | Decrease Join | Send Join(S,G) | Decrease Join | Decrease Join | 3197 | Timer to | to new next | Timer to | Timer to | 3198 | t_override | hop; Send | t_override | t_override | 3199 | | Prune(S,G) to | | | 3200 | | old next hop; | | | 3201 | | Set Join Timer | | | 3202 | | to t_periodic | | | 3203 | 3204 +-----------------+-----------------+-----------------+-----------------+ 3206 This state machine uses the following macro: 3208 bool JoinDesired(S,G) { 3209 return( immediate_olist(S,G) != NULL 3210 OR ( KeepaliveTimer(S,G) is running 3211 AND inherited_olist(S,G) != NULL ) ) 3212 } 3214 JoinDesired(S,G) is true when the router has forwarding state that would 3215 cause it to forward traffic for G using source tree state. The source 3216 tree state can either be as a result of active source-specific join 3217 state, or the (S,G) Keepalive Timer and active non-source-specific 3218 state. Note that although JoinDesired is true, the router's sending of a 3219 Join(S,G) message may be suppressed by another router sending a 3220 Join(S,G) onto the upstream interface. 3222 Transitions from NotJoined State 3224 When the upstream (S,G) state machine is in NotJoined state, the 3225 following event may trigger a state transition: 3227 JoinDesired(S,G) becomes True 3228 The macro JoinDesired(S,G) becomes True, e.g., because the | 3229 downstream state for (S,G) has changed so that at least one | 3230 interface is in inherited_olist(S,G). 3232 The upstream (S,G) state machine transitions to Joined state. 3233 Send Join(S,G) to the appropriate upstream neighbor, which is 3234 RPF'(S,G). Set the Join Timer (JT) to expire after t_periodic 3235 seconds. 3237 Transitions from Joined State 3239 When the upstream (S,G) state machine is in Joined state, the following 3240 events may trigger state transitions: 3242 JoinDesired(S,G) becomes False 3243 The macro JoinDesired(S,G) becomes False, e.g., because the | 3244 downstream state for (S,G) has changed so no interface is in | 3245 inherited_olist(S,G). 3247 The upstream (S,G) state machine transitions to NotJoined 3248 state. Send Prune(S,G) to the appropriate upstream neighbor, 3249 which is RPF'(S,G). Cancel the Join Timer (JT), and set 3250 SPTbit(S,G) to FALSE. 3252 Join Timer Expires 3253 The Join Timer (JT) expires, indicating time to send a 3254 Join(S,G) 3256 Send Join(S,G) to the appropriate upstream neighbor, which is 3257 RPF'(S,G). Restart the Join Timer (JT) to expire after 3258 t_periodic seconds. 3260 See Join(S,G) to RPF'(S,G) 3261 This event is only relevant if RPF_interface(S) is a shared 3262 medium. This router sees another router on RPF_interface(S) 3263 send a Join(S,G) to RPF'(S,G). This causes this router to 3264 suppress its own Join. 3266 The upstream (S,G) state machine remains in Joined state. 3268 Let t_joinsuppress be the minimum of t_suppressed and the 3269 HoldTime from the Join/Prune message triggering this event. 3271 If the Join Timer is set to expire in less than t_joinsuppress 3272 seconds, reset it so that it expires after t_joinsuppress 3273 seconds. If the Join Timer is set to expire in more than 3274 t_joinsuppress seconds, leave it unchanged. 3276 See Prune(S,G) to RPF'(S,G) 3277 This event is only relevant if RPF_interface(S) is a shared 3278 medium. This router sees another router on RPF_interface(S) 3279 send a Prune(S,G) to RPF'(S,G). As this router is in Joined 3280 state, it must override the Prune after a short random 3281 interval. 3283 The upstream (S,G) state machine remains in Joined state. If 3284 the Join Timer is set to expire in more than t_override 3285 seconds, reset it so that it expires after t_override seconds. 3287 See Prune(S,G,rpt) to RPF'(S,G) 3288 This event is only relevant if RPF_interface(S) is a shared 3289 medium. This router sees another router on RPF_interface(S) 3290 send a Prune(S,G,rpt) to RPF'(S,G). If the upstream router is 3291 an RFC 2362 compliant PIM router, then the Prune(S,G,rpt) will 3292 cause it to stop forwarding. For backwards compatibility, 3293 this router should override the prune so that forwarding 3294 continues. 3296 The upstream (S,G) state machine remains in Joined state. If 3297 the Join Timer is set to expire in more than t_override 3298 seconds, reset it so that it expires after t_override seconds. 3300 See Prune(*,G) to RPF'(S,G) 3301 This event is only relevant if RPF_interface(S) is a shared 3302 medium. This router sees another router on RPF_interface(S) 3303 send a Prune(*,G) to RPF'(S,G). If the upstream router is an 3304 RFC 2362 compliant PIM router, then the Prune(*,G) will cause 3305 it to stop forwarding. For backwards compatibility, this 3306 router should override the prune so that forwarding continues. 3308 The upstream (S,G) state machine remains in Joined state. If 3309 the Join Timer is set to expire in more than t_override 3310 seconds, reset it so that it expires after t_override seconds. 3312 RPF'(S,G) changes due to an Assert 3313 The current next hop towards S changes due to an Assert(S,G) 3314 on the RPF_interface(S). 3316 The upstream (S,G) state machine remains in Joined state. If 3317 the Join Timer is set to expire in more than t_override 3318 seconds, reset it so that it expires after t_override seconds. 3320 If the Join Timer is set to expire in less than t_override 3321 seconds, leave it unchanged. 3323 RPF'(S,G) changes not due to an Assert 3324 An event occurred which caused the next hop towards S to 3325 change. Note that this transition does not occur if an Assert 3326 is active and the upstream interface does not change. 3328 The upstream (S,G) state machine remains in Joined state. 3329 Send Join(S,G) to the new upstream neighbor which is the new 3330 value of RPF'(S,G). Send Prune(S,G) to the old upstream 3331 neighbor, which is the old value of RPF'(S,G). Set the Join 3332 Timer (JT) to expire after t_periodic seconds. 3334 RPF'(S,G) GenID changes 3335 The Generation ID of the router that is RPF'(S,G) changes. 3336 This normally means that this neighbor has lost state, and so 3337 the state must be refreshed. 3339 The upstream (S,G) state machine remains in Joined state. If 3340 the Join Timer is set to expire in more than t_override 3341 seconds, reset it so that it expires after t_override seconds. 3343 4.5.8. (S,G,rpt) Periodic Messages 3345 (S,G,rpt) Joins and Prunes are (S,G) Joins or Prunes sent on the RP tree 3346 with the RPT bit set, either to modify the results of (*,G) Joins, or to 3347 override the behavior of other upstream LAN peers. The next section 3348 describes the rules for sending triggered messages. This section 3349 describes the rules for including a Prune(S,G,rpt) message with a 3350 Join(*,G). 3352 When a router is going to send a Join(*,G), it should use the following 3353 pseudocode, for each (S,G) for which it has state, to decide whether to 3354 include a Prune(S,G,rpt) in the compound Join/Prune message: 3356 if( SPTbit(S,G) == TRUE ) { 3357 # Note: If receiving (S,G) on the SPT, we only prune off the 3358 # shared tree if the RPF neighbors differ. 3359 if( RPF'(*,G) != RPF'(S,G) ) { 3360 add Prune(S,G,rpt) to compound message 3361 } 3362 } else if ( inherited_olist(S,G,rpt) == NULL ) { 3363 # Note: all (*,G) olist interfaces received RPT prunes for (S,G). 3364 add Prune(S,G,rpt) to compound message 3365 } else if ( RPF'(*,G) != RPF'(S,G,rpt) { 3366 # Note: we joined the shared tree, but there was an (S,G) assert and 3367 # the source tree RPF neighbor is different. 3368 add Prune(S,G,rpt) to compound message 3369 } 3371 Note that Join(S,G,rpt) is not normally sent as a periodic message, but 3372 only as a triggered message. 3374 4.5.9. State Machine for (S,G,rpt) Triggered Messages 3376 The state machine for (S,G,rpt) triggered messages is required per-(S,G) 3377 when there is (*,G) or (*,*,RP) join state at a router, and the router 3378 or any of its upstream LAN peers wishes to prune S off the RP tree. 3380 There are three states in the state machine. One of the states is when 3381 there is neither (*,G) nor (*,*,RP(G)) join state at this router. If 3382 there is (*,G) or (*,*,RP(G)) join state at the router, then the state 3383 machine must be at one of the other two states. The three states are: 3385 Pruned(S,G,rpt) 3386 (*,G) or (*,*,RP(G)) Joined, but (S,G,rpt) pruned 3388 NotPruned(S,G,rpt) 3389 (*,G) or (*,*,RP(G)) Joined, and (S,G,rpt) not pruned 3391 RPTNotJoined(G) 3392 neither (*,G) nor (*,*,RP(G)) has been joined. 3394 In addition, there is an (S,G,rpt) Override Timer, OT(S,G,rpt), which is 3395 used to delay triggered Join(S,G,rpt) messages to prevent implosions of 3396 triggered messages. 3398 Figure 9: Upstream (S,G,rpt) state machine for triggered messages in 3399 tabular form 3401 +---------------++-------------------------------------------------------------+ 3402 | || Event | 3403 | ++---------------+---------------+--------------+--------------+ 3404 |Prev State || PruneDesired | PruneDesired | RPTJoin | inherited_ | 3405 | || (S,G,rpt) | (S,G,rpt) | Desired(G) | olist | 3406 | || ->True | ->False | ->False | (S,G,rpt) | 3407 | || | | | ->non-NULL | 3408 ->n+---------------++---------------+---------------+--------------+--------------+ 3409 |RPTNotJoined || -> P state | - | - | -> NP state | 3410 |(G) (NJ) || | | | | 3411 +---------------++---------------+---------------+--------------+--------------+ 3412 |Pruned || - | -> NP state | -> NJ state | - | 3413 |(S,G,rpt) (P) || | Send Join | | | 3414 | || | (S,G,rpt) | | | 3415 +---------------++---------------+---------------+--------------+--------------+ 3416 |NotPruned || -> P state | - | -> NJ state | - | 3417 |(S,G,rpt) || Send Prune | | Cancel OT | | 3418 |(NP) || (S,G,rpt); | | | | 3419 | || Cancel OT | | | | 3420 +---------------++---------------+---------------+--------------+--------------+ 3421 Additionally, we have the following transitions within the 3422 NotPruned(S,G,rpt) state which are all used for prune override behavior. 3424 t+-----------------------------------------------------------------------+ 3425 | In NotPruned(S,G,rpt) State | 3426 | 3427 +-----------+--------------+--------------+--------------+--------------+ 3428 |Override | See Prune | See Join | See Prune | RPF' | 3429 |Timer | (S,G,rpt) to | (S,G,rpt) to | (S,G) to | (S,G,rpt) -> | 3430 |expires | RPF' | RPF' | RPF' | RPF' (*,G) | 3431 | | (S,G,rpt) | (S,G,rpt) | (S,G,rpt) | | 3432 | 3433 +-----------+--------------+--------------+--------------+--------------+ 3434 |Send Join | OT = min(OT, | Cancel OT | OT = min(OT, | OT = min(OT, | 3435 |(S,G,rpt); | t_override) | | t_override) | t_override) | 3436 |Leave OT | | | | | 3437 |unset | | | | | 3438 | 3439 +-----------+--------------+--------------+--------------+--------------+ 3441 Note that the min function in the above state machine considers a non- 3442 running timer to have an infinite value (e.g. min(not-running, 3443 t_override) = t_override). 3445 This state machine uses the following macros: 3447 bool RPTJoinDesired(G) { 3448 return (JoinDesired(*,G) OR JoinDesired(*,*,RP(G))) 3449 } 3451 RPTJoinDesired(G) is true when the router has forwarding state that 3452 would cause it to forward traffic for G using either (*,G) or (*,*,RP) 3453 shared tree state. 3455 bool PruneDesired(S,G,rpt) { 3456 return ( RPTJoinDesired(G) AND 3457 ( inherited_olist(S,G,rpt) == NULL 3458 OR (SPTbit(S,G)==TRUE 3459 AND (RPF'(*,G) != RPF'(S,G)) ))) 3460 } 3462 PruneDesired(S,G,rpt) can only be true if RPTJoinDesired(G) is true. If 3463 RPTJoinDesired(G) is true, then PruneDesired(S,G,rpt) is true if either 3464 there are no outgoing interfaces that S would be forwarded on, or if the 3465 router has active (S,G) forwarding state but RPF'(*,G) != RPF'(S,G). 3467 The state machine contains the following transition events: 3469 See Join(S,G,rpt) to RPF'(S,G,rpt) 3470 This event is only relevant in the "Not Pruned" state. 3472 The router sees a Join(S,G,rpt) from someone else to RPF'(S,G,rpt), 3473 which is the correct upstream neighbor. If we're in "NotPruned" 3474 state and the (S,G,rpt) Override Timer is running, then this is 3475 because we have been triggered to send our own Join(S,G,rpt) to 3476 RPF'(S,G,rpt). Someone else beat us to it, so there's no need to 3477 send our own Join. 3479 The action is to cancel the Override Timer. 3481 See Prune(S,G,rpt) to RPF'(S,G,rpt) 3482 This event is only relevant in the "NotPruned" state. 3484 The router sees a Prune(S,G,rpt) from someone else to to 3485 RPF'(S,G,rpt), which is the correct upstream neighbor. If we're in 3486 the "NotPruned" state, then we want to continue to receive traffic 3487 from S destined for G, and that traffic is being supplied by 3488 RPF'(S,G,rpt). Thus we need to override the Prune. 3490 The action is to set the (S,G,rpt) Override Timer to the randomized 3491 prune-override interval, t_override. However if the Override Timer 3492 is already running, we only set the timer if doing so would set it 3493 to a lower value. At the end of this interval, if no-one else has 3494 sent a Join, then we will do so. 3496 See Prune(S,G) to RPF'(S,G,rpt) 3497 This event is only relevant in the "NotPruned" state. 3499 This transition and action are the same as the above transition and 3500 action, except that the Prune does not have the RPT bit set. This 3501 transition is necessary to be compatible with routers implemented 3502 from RFC2362 that don't maintain separate (S,G) and (S,G,rpt) 3503 state. 3505 The (S,G,rpt) prune Override Timer expires 3506 This event is only relevant in the "NotPruned" state. 3508 When the Override Timer expires, we must send a Join(S,G,rpt) to 3509 RPF'(S,G,rpt) to override the Prune message that caused the timer 3510 to be running. We only send this if RPF'(S,G,rpt) equals RPF'(*,G) 3511 - if this were not the case, then the Join might be sent to a 3512 router that does not have (*,G) or (*,*,RP(G)) Join state, and so 3513 the behavior would not be well defined. If RPF'(S,G,rpt) is not 3514 the same as RPF'(*,G), then it may stop forwarding S. However, if 3515 this happens, then the router will send an AssertCancel(S,G), which 3516 would then cause RPF'(S,G,rpt) to become equal to RPF'(*,G) (see 3517 below). 3519 RPF'(S,G,rpt) changes to become equal to RPF'(*,G) 3520 This event is only relevant in the "NotPruned" state. 3522 RPF'(S,G,rpt) can only be different from RPF'(*,G) if an (S,G) 3523 Assert has happened, which means that traffic from S is arriving on 3524 the SPT, and so Prune(S,G,rpt) will have been sent to RPF'(*,G). 3525 When RPF'(S,G,rpt) changes to become equal to RPF'(*,G), we need to 3526 trigger a Join(S,G,rpt) to RPF'(*,G) to cause that router to start 3527 forwarding S again. 3529 The action is to set the (S,G,rpt) Override Timer to the randomized 3530 prune-override interval t_override. However if the timer is 3531 already running, we only set the timer if doing so would set it to 3532 a lower value. At the end of this interval, if no-one else has 3533 sent a Join, then we will do so. 3535 PruneDesired(S,G,rpt)->TRUE 3536 See macro above. This event is relevant in the "NotPruned" and 3537 "RPTNotJoined(G)" states. 3539 The router wishes to receive traffic for G, but does not wish to 3540 receive traffic from S destined for G. This causes the router to 3541 transition into the Pruned state. 3543 If the router was previously in NotPruned state, then the action is 3544 to send a Prune(S,G,rpt) to RPF'(S,G,rpt), and to cancel the 3545 Override Timer. If the router was previously in RPTNotJoined(G) 3546 state, then there is no need to trigger an action in this state 3547 machine because sending a Prune(S,G,rpt) is handled by the rules 3548 for sending the Join(*,G) or Join(*,*,RP). 3550 PruneDesired(S,G,rpt)->FALSE 3551 See macro above. This transition is only relevant in the "Pruned" 3552 state. 3554 If the router is in the Pruned(S,G,rpt) state, and 3555 PruneDesired(S,G,rpt) changes to FALSE, this could be because the 3556 router no longer has RPTJoinDesired(G) true, or it now wishes to 3557 receive traffic from S again. If it is the former, then this 3558 transition should not happen, but instead the 3559 "RPTJoinDesired(G)->FALSE" transition should happen. Thus this 3560 transition should be interpreted as "PruneDesired(S,G,rpt)->FALSE 3561 AND RPTJoinDesired(G)==TRUE" 3563 The action is to send a Join(S,G,rpt) to RPF'(S,G,rpt). 3565 RPTJoinDesired(G)->FALSE 3566 This event is relevant in the "Pruned" and "NotPruned" states. 3568 The router no longer wishes to receive any traffic destined for G 3569 on the RP Tree. This causes a transition to the RPTNotJoined(G) 3570 state, and the Override Timer is canceled if it was running. Any 3571 further actions are handled by the appropriate upstream state 3572 machine for (*,G) or (*,*,RP). 3574 inherited_olist(S,G,rpt) becomes non-NULL 3575 This transition is only relevant in the RPTNotJoined(G) state. 3577 The router has joined the RP tree (handled by the (*,G) or (*,*,RP) 3578 upstream state machine as appropriate), and wants to receive 3579 traffic from S. This does not trigger any events in this state 3580 machine, but causes a transition to the NotPruned(S,G,rpt) state. 3582 4.5.10. Background: (*,*,RP) and (S,G,rpt) Interaction 3584 In sections 4.5.8 and 4.5.9 the mechanisms for sending periodic and 3585 triggered (S,G,rpt) messages are described. The astute reader will note 3586 that periodic Prune(S,G,rpt) messages are only sent in PIM Join/Prune 3587 messages containing a Join(*,G), whereas it is possible for a triggered 3588 Prune(S,G,rpt) message to be sent when the router has no (*,G) join 3589 state. This may seem like a contradiction, but in fact it is 3590 intentional, and is a side effect of not optimizing (*,*,RP) behavior. 3592 We first note that reception of a Join(*,*,RP) by itself does not cancel 3593 (S,G,rpt) prune state on that interface, whereas receiving a Join(*,G) 3594 by itself does cancel (S,G,rpt) prune state on that interface. 3595 Similarly, reception of a Prune(*,G) on an interface with (*,*,RP) join 3596 state does not by itself prevent forwarding of G using the (*,*,RP) 3597 state - this is because a Prune(*,G) only serves to cancel (*,G) join 3598 state. Conceptually (*,*,RP) state functions "above" the normal (*,G) 3599 and (S,G) mechanisms, and so neither Join(*,*,RP) or Prune(*,*,RP) 3600 messages affect any other state. 3602 The upshot of this is that to prevent forwarding (S,G) on (*,*,RP) 3603 state, a Prune(S,G,rpt) must be used. 3605 We also note that for historical reasons there is no Assert(*,*,RP) 3606 message, so any forwarding contention is resolved using Assert(*,G) 3607 messages. 3609 We now need to consider the interaction between (*,*,RP) state and (*,G) 3610 state. If there is a need for an assert between two upstream routers on 3611 a LAN, we need to ensure that the correct thing happens for all 3612 combinations of (*,*,RP) and (*,G) forwarding state. As there is no 3613 Assert(*,*,RP) message, no router can tell whether the assert winner has 3614 (*,*,RP) state or (*,G) state. Thus a downstream router has to treat 3615 the two the same and send its periodic Prune(S,G,rpt) messages to 3616 RPF'(*,G). 3618 To avoid needing to specify all the complex override rules between 3619 (*,*,RP), (*,G) and (S,G,rpt), we simply require that to prune (S,G) off 3620 the (*,*,RP) tree, a Join(*,G) must also be sent. 3622 If a router is receiving on (*,*,RP) state, and has not yet had (*,G) 3623 state instantiated, it may still need to send a triggered Join(S,G,rpt) 3624 to override a Prune(S,G,rpt) that it sees directed to RPF'(*,G) on its 3625 upstream interface. Hence triggered (S,G,rpt) messages may be sent when 3626 JoinDesired(*,G) is false but JoinDesired(*,*,RP) is true. 3628 Finally we note that there is an unoptimized case when the upstream 3629 router on a LAN already has (*,G) join and (S,G,rpt) prune state caused 3630 by an existing downstream router. If at this time a new Join(*,*,RP) is 3631 sent to the upstream router from a different downstream router, this 3632 will not override the (S,G,rpt) prune state at the upstream router. The 3633 override will not occur until the next time the original downstream 3634 router resends its Prune(S,G,rpt). This case was considered to be not 3635 worth optimizing, as (*,*,RP) state is generally very long lived, and so 3636 any minor delays in getting traffic to a new PMBR seem unimportant. 3638 4.6. PIM Assert Messages 3640 Where multiple PIM routers peer over a shared LAN it is possible for 3641 more than one upstream router to have valid forwarding state for a 3642 packet, which can lead to packet duplication (see Section 3 "Multi- 3643 access LANs"). PIM does not attempt to prevent this from occurring. 3644 Instead it detects when this has happened and elects a single forwarder 3645 amongst the upstream routers to prevent further duplication. This 3646 election is performed using PIM Assert messages. Assert messages are 3647 also received by downstream routers on the LAN, and these cause 3648 subsequent Join/Prune messages to be sent to the upstream router that 3649 won the Assert. 3651 In general, a PIM Assert message should only be accepted for processing 3652 if it comes from a known PIM neighbor. A PIM router hears about PIM 3653 neighbors through PIM Hello messages. If a router receives an Assert 3654 message from a particular IP source address and it has not seen a PIM 3655 Hello message from that source address, then the Assert message SHOULD 3656 be discarded without further processing. In addition, if the Hello | 3657 message from a neighbor was authenticated using the IPsec Authentication | 3658 Header (AH) (see Section 6.3) then all Assert messages from that 3659 neighbor MUST also be authenticated using IPsec AH. 3661 We note that some older PIM implementations incorrectly fail to send 3662 Hello messages on point-to-point interfaces, so we also RECOMMEND that a 3663 configuration option be provided to allow interoperation with such older 3664 routers, but that this configuration option SHOULD NOT be enabled by 3665 default. 3667 4.6.1. (S,G) Assert Message State Machine 3669 The (S,G) Assert state machine for interface I is shown in Figure 10. 3670 There are three states: 3672 NoInfo (NI) 3673 This router has no (S,G) assert state on interface I. 3675 I am Assert Winner (W) 3676 This router has won an (S,G) assert on interface I. It is now 3677 responsible for forwarding traffic from S destined for G out of 3678 interface I. Irrespective of whether it is the DR for I, while a 3679 router is the assert winner, it is also responsible for forwarding 3680 traffic onto I on behalf of local hosts on I that have made 3681 membership requests that specifically refer to S (and G). 3683 I am Assert Loser (L) 3684 This router has lost an (S,G) assert on interface I. It must not 3685 forward packets from S destined for G onto interface I. If it is 3686 the DR on I, it is no longer responsible for forwarding traffic 3687 onto I to satisfy local hosts with membership requests that 3688 specifically refer to S and G. 3690 In addition, there is also an Assert Timer (AT) that is used to time out 3691 asserts on the assert losers and to resend asserts on the assert winner. 3693 Figure 10: Per-interface (S,G) Assert State machine in tabular form 3695 F+-----------------------------------------------------------------------+ 3696 | In NoInfo (NI) State | 3697 | 3698 +---------------+-------------------+------------------+----------------+ 3699 | Receive | Receive Assert | Data arrives | Receive | 3700 | Inferior | with RPTbit | from S to G on | Acceptable | 3701 | Assert with | set and | I and | Assert with | 3702 | RPTbit clear | CouldAssert | CouldAssert | RPTbit clear | 3703 | and | (S,G,I) | (S,G,I) | and AssTrDes | 3704 | CouldAssert | | | (S,G,I) | 3705 | (S,G,I) | | | | 3706 | 3707 +---------------+-------------------+------------------+----------------+ 3708 | -> W state | -> W state | -> W state | -> L state | 3709 | [Actions A1] | [Actions A1] | [Actions A1] | [Actions A6] | 3710 | 3711 +---------------+-------------------+------------------+----------------+ 3713 -+-----------------------------------------------------------------------+ 3714 | In I Am Assert Winner (W) State | 3715 | 3716 +----------------+------------------+-----------------+-----------------+ 3717 | Assert Timer | Receive | Receive | CouldAssert | 3718 | Expires | Inferior | Preferred | (S,G,I) -> | 3719 | | Assert | Assert | FALSE | 3720 | 3721 +----------------+------------------+-----------------+-----------------+ 3722 | -> W state | -> W state | -> L state | -> NI state | 3723 | [Actions A3] | [Actions A3] | [Actions A2] | [Actions A4] | 3724 | 3725 +----------------+------------------+-----------------+-----------------+ 3727 -+-------------------------------------------------------------------------+ 3728 | In I Am Assert Loser (L) State | 3729 | 3730 +-------------+--------------+--------------+--------------+--------------+ 3731 |Receive | Receive | Receive | Assert Timer | Current | 3732 |Preferred | Acceptable | Inferior | Expires | Winner's | 3733 |Assert | Assert from | Assert from | | GenID | 3734 | | Current | Current | | Changes or | 3735 | | Winner | Winner | | NLT Expires | 3736 | 3737 +-------------+--------------+--------------+--------------+--------------+ 3738 |-> L state | -> L state | -> NI state | -> NI state | -> NI state | 3739 |[Actions A2] | [Actions A2] | [Actions A5] | [Actions A5] | [Actions A5] | 3740 A5]+-------------+--------------+--------------+--------------+--------------+ 3741 T+-----------------------------------------------------------------------+ 3742 | In I Am Assert Loser (L) State | 3743 | 3744 +----------------+-----------------+-------------------+----------------+ 3745 | AssTrDes | my_metric -> | RPF_interface | Receive | 3746 | (S,G,I) -> | better than | (S) stops | Join(S,G) on | 3747 | FALSE | winner's | being I | interface I | 3748 | | metric | | | 3749 | 3750 +----------------+-----------------+-------------------+----------------+ 3751 | -> NI state | -> NI state | -> NI state | -> NI State | 3752 | [Actions A5] | [Actions A5] | [Actions A5] | [Actions A5] | 3753 | 3754 +----------------+-----------------+-------------------+----------------+ 3756 Note that for reasons of compactness, "AssTrDes(S,G,I)" is used in the 3757 state machine table to refer to AssertTrackingDesired(S,G,I). 3759 Terminology: 3760 A "preferred assert" is one with a better metric than the current 3761 winner. 3763 An "acceptable assert" is one that has a better metric than 3764 my_assert_metric(S,G,I). 3766 An "inferior assert" is one with a worse metric than 3767 my_assert_metric(S,G,I). 3768 The state machine uses the following macros: 3770 CouldAssert(S,G,I) = 3771 SPTbit(S,G)==TRUE 3772 AND (RPF_interface(S) != I) 3773 AND (I in ( ( joins(*,*,RP(G)) (+) joins(*,G) (-) prunes(S,G,rpt) ) 3774 (+) ( pim_include(*,G) (-) pim_exclude(S,G) ) 3775 (-) lost_assert(*,G) 3776 (+) joins(S,G) (+) pim_include(S,G) ) ) 3778 CouldAssert(S,G,I) is true for downstream interfaces which would be in 3779 the inherited_olist(S,G) if (S,G) assert information was not taken into 3780 account. 3782 AssertTrackingDesired(S,G,I) = 3783 (I in ( ( joins(*,*,RP(G)) (+) joins(*,G) (-) prunes(S,G,rpt) ) 3784 (+) ( pim_include(*,G) (-) pim_exclude(S,G) ) 3785 (-) lost_assert(*,G) 3786 (+) joins(S,G) ) ) 3787 OR (local_receiver_include(S,G,I) == TRUE 3788 AND (I_am_DR(I) OR (AssertWinner(S,G,I) == me))) 3789 OR ((RPF_interface(S) == I) AND (JoinDesired(S,G) == TRUE)) 3790 OR ((RPF_interface(RP(G)) == I) AND (JoinDesired(*,G) == TRUE) 3791 AND (SPTbit(S,G) == FALSE)) 3793 AssertTrackingDesired(S,G,I) is true on any interface in which an (S,G) 3794 assert might affect our behavior. 3796 The first three lines of AssertTrackingDesired account for (*,G) join 3797 and local membership information received on I that might cause the 3798 router to be interested in asserts on I. 3800 The 4th line accounts for (S,G) join information received on I that 3801 might cause the router to be interested in asserts on I. 3803 The 5th and 6th lines account for (S,G) local membership information on 3804 I. Note that we can't use the pim_include(S,G) macro since it uses 3805 lost_assert(S,G,I) and would result in the router forgetting that it 3806 lost an assert if the only reason it was interested was local 3807 membership. The AssertWinner(S,G,I) check forces an assert winner to 3808 keep on being responsible for forwarding as long as local receivers are 3809 present. Removing this check would make the assert winner give up 3810 forwarding as soon as the information that originally caused it to 3811 forward went away and the task of forwarding for local receivers would 3812 revert back to the DR. 3814 The last three lines account for the fact that a router must keep track 3815 of assert information on upstream interfaces in order to send joins and 3816 prunes to the proper neighbor. 3818 Transitions from NoInfo State 3820 When in NoInfo state, the following events may trigger transitions: 3822 Receive Inferior Assert with RPTbit cleared AND 3823 CouldAssert(S,G,I)==TRUE 3824 An assert is received for (S,G) with the RPT bit cleared that 3825 is inferior to our own assert metric. The RPT bit cleared 3826 indicates that the sender of the assert had (S,G) forwarding 3827 state on this interface. If the assert is inferior to our 3828 metric, then we must also have (S,G) forwarding state (i.e. 3829 CouldAssert(S,G,I)==TRUE) as (S,G) asserts beat (*,G) asserts, 3830 and so we should be the assert winner. We transition to the 3831 "I am Assert Winner" state, and perform Actions A1 (below). 3833 Receive Assert with RPTbit set AND CouldAssert(S,G,I)==TRUE 3834 An assert is received for (S,G) on I with the RPT bit set 3835 (it's a (*,G) assert). CouldAssert(S,G,I) is TRUE only if we 3836 have (S,G) forwarding state on this interface, so we should be 3837 the assert winner. We transition to the "I am Assert Winner" 3838 state, and perform Actions A1 (below). 3840 An (S,G) data packet arrives on interface I, AND 3841 CouldAssert(S,G,I)==TRUE 3842 An (S,G) data packet arrived on an downstream interface which 3843 is in our (S,G) outgoing interface list. We optimistically 3844 assume that we will be the assert winner for this (S,G), and 3845 so we transition to the "I am Assert Winner" state, and 3846 perform Actions A1 (below) which will initiate the assert 3847 negotiation for (S,G). | 3849 Receive Acceptable Assert with RPT bit clear AND | 3850 AssertTrackingDesired(S,G,I)==TRUE | 3851 We're interested in (S,G) Asserts, either because I is a 3852 downstream interface for which we have (S,G) or (*,G) 3853 forwarding state, or because I is the upstream interface for S 3854 and we have (S,G) forwarding state. The received assert has a 3855 better metric than our own, so we do not win the Assert. We 3856 transition to "I am Assert Loser" and perform actions A6 3857 (below). 3859 Transitions from "I am Assert Winner" State 3861 When in "I am Assert Winner" state, the following events trigger 3862 transitions: 3864 Assert Timer Expires 3865 The (S,G) Assert Timer expires. As we're in the Winner state, 3866 then we must still have (S,G) forwarding state that is 3867 actively being kept alive. We re-send the (S,G) Assert and 3868 restart the Assert Timer (Action A3 below). Note that the 3869 assert winner's Assert Timer is engineered to expire shortly 3870 before timers on assert losers; this prevents unnecessary 3871 thrashing of the forwarder and periodic flooding of duplicate 3872 packets. 3874 Receive Inferior Assert 3875 We receive an (S,G) assert or (*,G) assert mentioning S that 3876 has a worse metric than our own. Whoever sent the assert is 3877 in error, and so we re-send an (S,G) Assert, and restart the 3878 Assert Timer (Action A3 below). 3880 Receive Preferred Assert 3881 We receive an (S,G) assert that has a better metric than our 3882 own. We transition to "I am Assert Loser" state and perform 3883 actions A2 (below). Note that this may affect the value of 3884 JoinDesired(S,G) and PruneDesired(S,G,rpt) which could cause 3885 transitions in the upstream (S,G) or (S,G,rpt) state machines. 3887 CouldAssert(S,G,I) -> FALSE 3888 Our (S,G) forwarding state or RPF interface changed so as to 3889 make CouldAssert(S,G,I) become false. We can no longer 3890 perform the actions of the assert winner, and so we transition 3891 to NoInfo state and perform actions A4 (below). This includes 3892 sending a "canceling assert" with an infinite metric. 3894 Transitions from "I am Assert Loser" State 3896 When in "I am Assert Loser" state, the following transitions can occur: 3898 Receive Preferred Assert 3899 We receive an assert that is better than that of the current 3900 assert winner. We stay in Loser state, and perform actions A2 3901 below. 3903 Receive Acceptable Assert from Current Winner 3904 We receive an assert from the current assert winner that is 3905 better than our own metric for this (S,G) (although the metric 3906 may be worse than the winner's previous metric). We stay in 3907 Loser state, and perform actions A2 below. 3909 Receive Inferior Assert from Current Winner 3910 We receive an assert from the current assert winner that is 3911 worse than our own metric for this group (typically the 3912 winner's metric became worse). We transition to NoInfo state, 3913 deleting the (S,G) assert information and allowing the normal 3914 PIM Join/Prune mechanisms to operate. Usually we will 3915 eventually re-assert and win when data packets from S have 3916 started flowing again. 3918 Assert Timer Expires 3919 The (S,G) Assert Timer expires. We transition to NoInfo 3920 state, deleting the (S,G) assert information (action A5 3921 below). 3923 Current Winner's GenID Changes or NLT Expires 3924 The Neighbor Liveness Timer associated with the current winner 3925 expires or we receive a Hello message from the current winner 3926 reporting a different GenID from the one it previously 3927 reported. This indicates that the current winner's interface 3928 or router has gone down (and may have come back up), and so we 3929 must assume it no longer knows it was the winner. We 3930 transition to the NoInfo state, deleting this (S,G) assert 3931 information (action A5 below). 3933 AssertTrackingDesired(S,G,I)->FALSE 3934 AssertTrackingDesired(S,G,I) becomes FALSE. Our forwarding 3935 state has changed so that (S,G) Asserts on interface I are no 3936 longer of interest to us. We transition to the NoInfo state, 3937 deleting the (S,G) assert information. 3939 My metric becomes better than the assert winner's metric 3940 my_assert_metric(S,G,I) has changed so that now my assert 3941 metric for (S,G) is better than the metric we have stored for 3942 current assert winner. This might happen the underlying 3943 routing metric changes, or when CouldAssert(S,G,I) becomes 3944 true; for example, when SPTbit(S,G) becomes true. We 3945 transition to NoInfo state, delete this (S,G) assert state 3946 (action A5 below), and allow the normal PIM Join/Prune 3947 mechanisms to operate. Usually we will eventually re-assert 3948 and win when data packets from S have started flowing again. 3950 RPF_interface(S) stops being interface I 3951 Interface I used to be the RPF interface for S, and now it is 3952 not. We transition to NoInfo state, deleting this (S,G) 3953 assert state (action A5 below). 3955 Receive Join(S,G) on Interface I 3956 We receive a Join(S,G) that has the Upstream Neighbor Address 3957 field set to one my IP address on interface I. The action is 3958 to transition to NoInfo state, and delete this (S,G) assert 3959 state (action A5 below), and allow the normal PIM Join/Prune 3960 mechanisms to operate. If whoever sent the Join was in error, 3961 then the normal assert mechanism will eventually re-apply and 3962 we will lose the assert again. However whoever sent the 3963 assert may know that the previous assert winner has died, and 3964 so we may end up being the new forwarder. 3966 (S,G) Assert State machine Actions 3968 A1: Send Assert(S,G) 3969 Set Assert Timer to (Assert_Time - Assert_Override_Interval) 3970 Store self as AssertWinner(S,G,I) 3971 Store spt_assert_metric(S,I) as AssertWinnerMetric(S,G,I) 3973 A2: Store new assert winner as AssertWinner(S,G,I) and assert 3974 winner metric as AssertWinnerMetric(S,G,I). 3975 Set Assert Timer to Assert_Time 3977 A3: Send Assert(S,G) 3978 Set Assert Timer to (Assert_Time - Assert_Override_Interval) 3980 A4: Send AssertCancel(S,G) 3981 Delete assert info (AssertWinner(S,G,I) and 3982 AssertWinnerMetric(S,G,I) will then return their default 3983 values). 3985 A5: Delete assert info (AssertWinner(S,G,I) and 3986 AssertWinnerMetric(S,G,I) will then return their default 3987 values). 3989 A6: Store new assert winner as AssertWinner(S,G,I) and assert 3990 winner metric as AssertWinnerMetric(S,G,I). 3991 Set Assert Timer to Assert_Time 3992 If (I is RPF_interface(S)) AND (UpstreamJPState(S,G) == true) | 3993 set SPTbit(S,G) to TRUE. 3995 Note that some of these actions may cause the value of JoinDesired(S,G), 3996 PruneDesired(S,G,rpt), or RPF'(S,G) to change, which could cause further 3997 transitions in other state machines. 3999 4.6.2. (*,G) Assert Message State Machine 4001 The (*,G) Assert state machine for interface I is shown in Figure 11. 4002 There are three states: 4004 NoInfo (NI) 4005 This router has no (*,G) assert state on interface I. 4007 I am Assert Winner (W) 4008 This router has won an (*,G) assert on interface I. It is now 4009 responsible for forwarding traffic destined for G onto interface I 4010 with the exception of traffic for which it has (S,G) "I am Assert 4011 Loser" state. Irrespective of whether it is the DR for I, it is 4012 also responsible for handling the membership requests for G from 4013 local hosts on I. 4015 I am Assert Loser (L) 4016 This router has lost an (*,G) assert on interface I. It must not 4017 forward packets for G onto interface I with the exception of 4018 traffic from sources for which is has (S,G) "I am Assert Winner" 4019 state. If it is the DR, it is no longer responsible for handling 4020 the membership requests for group G from local hosts on I. 4022 In addition, there is also an Assert Timer (AT) that is used to time out 4023 asserts on the assert losers and to resend asserts on the assert winner. 4025 When an Assert message is received with a source address other than 4026 zero, a PIM implementation must first match it against the possible 4027 events in the (S,G) assert state machine and process any transitions and 4028 actions, before considering whether the Assert message matches against 4029 the (*,G) assert state machine. 4031 It is important to note that NO TRANSITION CAN OCCUR in the (*,G) state 4032 machine as a result of receiving an Assert message unless the (S,G) 4033 assert state machine for the relevant S and G is in the "NoInfo" state 4034 after the (S,G) state machine has processed the message. Also NO 4035 TRANSITION CAN OCCUR in the (*,G) state machine as a result of receiving 4036 an assert message if that message triggers any change of state in the 4037 (S,G) state machine. Obviously when the source address in the received | 4038 message is set to zero an (S,G) state machine for the S and G does not | 4039 exist and can be assumed to be in the "NoInfo" state. 4041 For example, if both the (S,G) and (*,G) assert state machines where in 4042 the NoInfo state when an Assert message arrives, and the message causes 4043 the (S,G) state machine to transition to either "W" or "L" state, then 4044 the assert would not be processed by the (*,G) assert state machine. 4046 Another example: if the (S,G) assert state machine is in "L" state when 4047 an assert message is received, and the assert metric in the message is 4048 worse than my_assert_metric(S,G,I), then the (S,G) assert state machine 4049 will transition to NoInfo state. In such a case if the (*,G) assert 4050 state machine were in NoInfo state, it might appear that it would 4051 transition to "W" state, but this is not the case because this message 4052 already triggered a transition in the (S,G) assert state machine. 4054 Figure 11: Per-interface (*,G) Assert State machine in tabular form 4056 F+-----------------------------------------------------------------------+ 4057 | In NoInfo (NI) State | 4058 | 4059 +-----------------------+-----------------------+-----------------------+ 4060 | Receive Inferior | Data arrives for G | Receive Acceptable | 4061 | Assert with RPTbit | on I and | Assert with RPTbit | 4062 | set and | CouldAssert | set and AssTrDes | 4063 | CouldAssert(*,G,I) | (*,G,I) | (*,G,I) | 4064 | 4065 +-----------------------+-----------------------+-----------------------+ 4066 | -> W state | -> W state | -> L state | 4067 | [Actions A1] | [Actions A1] | [Actions A2] | 4068 | 4069 +-----------------------+-----------------------+-----------------------+ 4071 -+-----------------------------------------------------------------------+ 4072 | In I Am Assert Winner (W) State | 4073 | 4074 +----------------+------------------+-----------------+-----------------+ 4075 | Assert Timer | Receive | Receive | CouldAssert | 4076 | Expires | Inferior | Preferred | (*,G,I) -> | 4077 | | Assert | Assert | FALSE | 4078 | 4079 +----------------+------------------+-----------------+-----------------+ 4080 | -> W state | -> W state | -> L state | -> NI state | 4081 | [Actions A3] | [Actions A3] | [Actions A2] | [Actions A4] | 4082 | 4083 +----------------+------------------+-----------------+-----------------+ 4085 -+-------------------------------------------------------------------------+ 4086 | In I Am Assert Loser (L) State | 4087 | 4088 +-------------+--------------+--------------+--------------+--------------+ 4089 |Receive | Receive | Receive | Assert Timer | Current | 4090 |Preferred | Acceptable | Inferior | Expires | Winner's | 4091 |Assert | Assert from | Assert from | | GenID | 4092 | | Current | Current | | Changes or | 4093 | | Winner | Winner | | NLT Expires | 4094 | 4095 +-------------+--------------+--------------+--------------+--------------+ 4096 |-> L state | -> L state | -> NI state | -> NI state | -> NI state | 4097 |[Actions A2] | [Actions A2] | [Actions A5] | [Actions A5] | [Actions A5] | 4098 A5]+-------------+--------------+--------------+--------------+--------------+ 4099 T+-----------------------------------------------------------------------+ 4100 | In I Am Assert Loser (L) State | 4101 | 4102 +----------------+----------------+------------------+------------------+ 4103 | AssTrDes | my_metric -> | RPF_interface | Receive | 4104 | (*,G,I) -> | better than | (RP(G)) stops | Join(*,G) or | 4105 | FALSE | Winner's | being I | Join | 4106 | | metric | | (*,*,RP(G)) on | 4107 | | | | Interface I | 4108 | 4109 +----------------+----------------+------------------+------------------+ 4110 | -> NI state | -> NI state | -> NI state | -> NI State | 4111 | [Actions A5] | [Actions A5] | [Actions A5] | [Actions A5] | 4112 | 4113 +----------------+----------------+------------------+------------------+ 4115 The state machine uses the following macros: 4117 CouldAssert(*,G,I) = 4118 ( I in ( joins(*,*,RP(G)) (+) joins(*,G) 4119 (+) pim_include(*,G)) ) 4120 AND (RPF_interface(RP(G)) != I) 4122 CouldAssert(*,G,I) is true on downstream interfaces for which we have 4123 (*,*,RP(G)) or (*,G) join state, or local members that requested any 4124 traffic destined for G. 4126 AssertTrackingDesired(*,G,I) = 4127 CouldAssert(*,G,I) 4128 OR (local_receiver_include(*,G,I)==TRUE 4129 AND (I_am_DR(I) OR AssertWinner(*,G,I) == me)) 4130 OR (RPF_interface(RP(G)) == I AND RPTJoinDesired(G)) 4132 AssertTrackingDesired(*,G,I) is true on any interface on which an (*,G) 4133 assert might affect our behavior. 4135 Note that for reasons of compactness, "AssTrDes(*,G,I)" is used in the 4136 state machine table to refer to AssertTrackingDesired(*,G,I). 4138 Terminology: 4139 A "preferred assert" is one with a better metric than the current 4140 winner. 4142 An "acceptable assert" is one that has a better metric than 4143 my_assert_metric(S,G,I). 4145 An "inferior assert" is one with a worse metric than 4146 my_assert_metric(S,G,I). 4148 Transitions from NoInfo State 4150 When in NoInfo state, the following events trigger transitions, but only 4151 if the (S,G) assert state machine is in NoInfo state before and after 4152 consideration of the received message: 4154 Receive Inferior Assert with RPTbit set AND 4155 CouldAssert(*,G,I)==TRUE 4156 An Inferior (*,G) assert is received for G on Interface I. If 4157 CouldAssert(*,G,I) is TRUE, then I is our downstream 4158 interface, and we have (*,G) forwarding state on this 4159 interface, so we should be the assert winner. We transition 4160 to the "I am Assert Winner" state, and perform Actions A1 4161 (below). 4163 A data packet destined for G arrives on interface I, AND 4164 CouldAssert(*,G,I)==TRUE 4165 A data packet destined for G arrived on a downstream interface 4166 which is in our (*,G) outgoing interface list. We therefore 4167 believe we should be the forwarder for this (*,G), and so we 4168 transition to the "I am Assert Winner" state, and perform 4169 Actions A1 (below). | 4171 Receive Acceptable Assert with RPT bit set AND | 4172 AssertTrackingDesired(*,G,I)==TRUE | 4173 We're interested in (*,G) Asserts, either because I is a 4174 downstream interface for which we have (*,G) forwarding state, 4175 or because I is the upstream interface for RP(G) and we have 4176 (*,G) forwarding state. We get a (*,G) Assert that has a 4177 better metric than our own, so we do not win the Assert. We 4178 transition to "I am Assert Loser" and perform actions A2 4179 (below). 4181 Transitions from "I am Assert Winner" State 4183 When in "I am Assert Winner" state, the following events trigger 4184 transitions, but only if the (S,G) assert state machine is in NoInfo 4185 state before and after consideration of the received message: 4187 Receive Inferior Assert 4188 We receive a (*,G) assert that has a worse metric than our 4189 own. Whoever sent the assert has lost, and so we re-send a 4190 (*,G) Assert, and restart the Assert Timer (Action A3 below). 4192 Receive Preferred Assert 4193 We receive a (*,G) assert that has a better metric than our 4194 own. We transition to "I am Assert Loser" state and perform 4195 actions A2 (below). 4197 When in "I am Assert Winner" state, the following events trigger 4198 transitions: 4200 Assert Timer Expires 4201 The (*,G) Assert Timer expires. As we're in the Winner state, 4202 then we must still have (*,G) forwarding state that is 4203 actively being kept alive. To prevent unnecessary thrashing 4204 of the forwarder and periodic flooding of duplicate packets, 4205 we re-send the (*,G) Assert, and restart the Assert Timer 4206 (Action A3 below). 4208 CouldAssert(*,G,I) -> FALSE 4209 Our (*,G) forwarding state or RPF interface changed so as to 4210 make CouldAssert(*,G,I) become false. We can no longer 4211 perform the actions of the assert winner, and so we transition 4212 to NoInfo state and perform actions A4 (below). 4214 Transitions from "I am Assert Loser" State 4216 When in "I am Assert Loser" state, the following events trigger 4217 transitions, but only if the (S,G) assert state machine is in NoInfo 4218 state before and after consideration of the received message: 4220 Receive Preferred Assert 4221 We receive a (*,G) assert that is better than that of the 4222 current assert winner. We stay in Loser state, and perform 4223 actions A2 below. 4225 Receive Acceptable Assert from Current Winner 4226 We receive a (*,G) assert from the current assert winner that 4227 is better than our own metric for this group (although the 4228 metric may be worse than the winner's previous metric). We 4229 stay in Loser state, and perform actions A2 below. 4231 Receive Inferior Assert from Current Winner 4232 We receive an assert from the current assert winner that is 4233 worse than our own metric for this group (typically because 4234 the winner's metric became worse). We transition to NoInfo 4235 state, delete this (*,G) assert state (action A5), and allow 4236 the normal PIM Join/Prune mechanisms to operate. Usually we 4237 will eventually re-assert and win when data packets for G have 4238 started flowing again. 4240 When in "I am Assert Loser" state, the following events trigger 4241 transitions: 4243 Assert Timer Expires 4244 The (*,G) Assert Timer expires. We transition to NoInfo state 4245 and delete this (*,G) assert info (action A5). 4247 Current Winner's GenID Changes or NLT Expires 4248 The Neighbor Liveness Timer associated with the current winner 4249 expires or we receive a Hello message from the current winner 4250 reporting a different GenID from the one it previously 4251 reported. This indicates that the current winner's interface 4252 or router has gone down (and may have come back up), and so we 4253 must assume it no longer knows it was the winner. We 4254 transition to the NoInfo state, deleting the (*,G) assert 4255 information (action A5). 4257 AssertTrackingDesired(*,G,I)->FALSE 4258 AssertTrackingDesired(*,G,I) becomes FALSE. Our forwarding 4259 state has changed so that (*,G) Asserts on interface I are no 4260 longer of interest to us. We transition to NoInfo state and 4261 delete this (*,G) assert info (action A5). 4263 My metric becomes better than the assert winner's metric 4264 My routing metric, rpt_assert_metric(G,I), has changed so that 4265 now my assert metric for (*,G) is better than the metric we 4266 have stored for current assert winner. We transition to 4267 NoInfo state, and delete this (*,G) assert state (action A5), 4268 and allow the normal PIM Join/Prune mechanisms to operate. 4269 Usually we will eventually re-assert and win when data packets 4270 for G have started flowing again. 4272 RPF_interface(RP(G)) stops being interface I 4273 Interface I used to be the RPF interface for RP(G), and now it 4274 is not. We transition to NoInfo state, and delete this (*,G) 4275 assert state (action A5). 4277 Receive Join(*,G) or Join(*,*,RP(G)) on interface I 4278 We receive a Join(*,G) or a Join(*,*,RP(G)) that has the 4279 Upstream Neighbor Address field set to my IP address on 4280 interface I. The action is to transition to NoInfo state, and 4281 delete this (*,G) assert state (action A5), and allow the 4282 normal PIM Join/Prune mechanisms to operate. If whoever sent 4283 the Join was in error, then the normal assert mechanism will 4284 eventually re-apply and we will lose the assert again. 4285 However whoever sent the assert may know that the previous 4286 assert winner has died, and so we may end up being the new 4287 forwarder. 4289 (*,G) Assert State machine Actions 4291 A1: Send Assert(*,G) 4292 Set Assert Timer to (Assert_Time - Assert_Override_Interval) 4293 Store self as AssertWinner(*,G,I). 4294 Store rpt_assert_metric(G,I) as AssertWinnerMetric(*,G,I). 4296 A2: Store new assert winner as AssertWinner(*,G,I) and assert 4297 winner metric as AssertWinnerMetric(*,G,I). 4298 Set Assert Timer to Assert_Time 4300 A3: Send Assert(*,G) 4301 Set Assert Timer to (Assert_Time - Assert_Override_Interval) 4303 A4: Send AssertCancel(*,G) 4304 Delete assert info (AssertWinner(*,G,I) and 4305 AssertWinnerMetric(*,G,I) will then return their default 4306 values). 4308 A5: Delete assert info (AssertWinner(*,G,I) and 4309 AssertWinnerMetric(*,G,I) will then return their default 4310 values). 4312 Note that some of these actions may cause the value of JoinDesired(*,G) 4313 or RPF'(*,G)) to change, which could cause further transitions in other 4314 state machines. 4316 4.6.3. Assert Metrics 4318 Assert metrics are defined as: 4320 struct assert_metric { 4321 rpt_bit_flag; 4322 metric_preference; 4323 route_metric; 4324 ip_address; 4325 }; 4327 When comparing assert_metrics, the rpt_bit_flag, metric_preference, and 4328 route_metric field are compared in order, where the first lower value 4329 wins. If all fields are equal, the primary IP address of the router 4330 that sourced the Assert message is used as a tie-breaker, with the 4331 highest IP address winning. 4333 An assert metric for (S,G) to include in (or compare against) an Assert 4334 message sent on interface I should be computed using the following 4335 pseudocode: 4337 assert_metric 4338 my_assert_metric(S,G,I) { 4339 if( CouldAssert(S,G,I) == TRUE ) { 4340 return spt_assert_metric(S,I) 4341 } else if( CouldAssert(*,G,I) == TRUE ) { 4342 return rpt_assert_metric(G,I) 4343 } else { 4344 return infinite_assert_metric() 4345 } 4346 } 4348 spt_assert_metric(S,I) gives the assert metric we use if we're sending 4349 an assert based on active (S,G) forwarding state: 4351 assert_metric 4352 spt_assert_metric(S,I) { 4353 return {0,MRIB.pref(S),MRIB.metric(S),my_ip_address(I)} 4354 } 4356 rpt_assert_metric(G,I) gives the assert metric we use if we're sending 4357 an assert based only on (*,G) forwarding state: 4359 assert_metric 4360 rpt_assert_metric(G,I) { 4361 return {1,MRIB.pref(RP(G)),MRIB.metric(RP(G)),my_ip_address(I)} 4362 } 4364 MRIB.pref(X) and MRIB.metric(X) are the routing preference and routing 4365 metrics associated with the route to a particular (unicast) destination 4366 X, as determined by the MRIB. my_ip_address(I) is simply the router's 4367 primary IP address that is associated with the local interface I. 4369 infinite_assert_metric() gives the assert metric we need to send an 4370 assert but don't match either (S,G) or (*,G) forwarding state: 4372 assert_metric 4373 infinite_assert_metric() { 4374 return {1,infinity,infinity,0} 4375 } 4377 4.6.4. AssertCancel Messages 4379 An AssertCancel message is simply an RPT Assert message but with 4380 infinite metric. It is sent by the assert winner when it deletes the 4381 forwarding state that had caused the assert to occur. Other routers 4382 will see this metric, and it will cause any other router that has 4383 forwarding state to send its own assert, and to take over forwarding. 4385 An AssertCancel(S,G) is an infinite metric assert with the RPT bit set 4386 that names S as the source. 4388 An AssertCancel(*,G) is an infinite metric assert with the RPT bit set | 4389 and the source set to zero. 4391 AssertCancel messages are simply an optimization. The original Assert 4392 timeout mechanism will allow a subnet to eventually become consistent; 4393 the AssertCancel mechanism simply causes faster convergence. No special 4394 processing is required for an AssertCancel message, since it is simply 4395 an Assert message from the current winner. 4397 4.6.5. Assert State Macros 4399 The macros lost_assert(S,G,rpt,I), lost_assert(S,G,I), and 4400 lost_assert(*,G,I) are used in the olist computations of Section 4.1, 4401 and are defined as: 4403 bool lost_assert(S,G,rpt,I) { 4404 if ( RPF_interface(RP(G)) == I OR 4405 ( RPF_interface(S) == I AND SPTbit(S,G) == TRUE ) ) { 4406 return FALSE 4407 } else { 4408 return ( AssertWinner(S,G,I) != NULL AND 4409 AssertWinner(S,G,I) != me ) 4410 } 4411 } 4413 bool lost_assert(S,G,I) { 4414 if ( RPF_interface(S) == I ) { 4415 return FALSE 4416 } else { 4417 return ( AssertWinner(S,G,I) != NULL AND 4418 AssertWinner(S,G,I) != me AND 4419 (AssertWinnerMetric(S,G,I) is better 4420 than spt_assert_metric(S,I) ) 4421 } 4422 } 4424 Note: the term "AssertWinnerMetric(S,G,I) is better than 4425 spt_assert_metric(S,I)" is required to correctly handle the transition 4426 phase when a router has (S,G) join state, but has not yet set the SPT 4427 bit. In this case it needs to ignore the assert state if it will win | 4428 the assert once the SPTbit is set. 4430 bool lost_assert(*,G,I) { 4431 if ( RPF_interface(RP(G)) == I ) { 4432 return FALSE 4433 } else { 4434 return ( AssertWinner(*,G,I) != NULL AND 4435 AssertWinner(*,G,I) != me ) 4436 } 4437 } 4439 AssertWinner(S,G,I) is the IP source address of the Assert(S,G) packet 4440 that won an Assert. 4442 AssertWinner(*,G,I) is the IP source address of the Assert(*,G) packet 4443 that won an Assert. 4445 AssertWinnerMetric(S,G,I) is the Assert metric of the Assert(S,G) packet 4446 that won an Assert. 4448 AssertWinnerMetric(*,G,I) is the Assert metric of the Assert(*,G) packet 4449 that won an Assert. 4451 AssertWinner(S,G,I) defaults to NULL and AssertWinnerMetric(S,G,I) 4452 defaults to Infinity when in the NoInfo state. 4454 Summary of Assert Rules and Rationale 4456 This section summarizes the key rules for sending and reacting to 4457 asserts and the rationale for these rules. This section is not intended 4458 to be and should not be treated as a definitive specification of 4459 protocol behavior. The state machines and pseudocode should be 4460 consulted for that purpose. Rather, this section is intended to 4461 document important aspects of a the Assert protocol behavior and to 4462 provide information that may prove helpful to the reader in 4463 understanding and implementing this part of the protocol. 4465 1. Behavior: Downstream neighbors send Join(*,G) and Join(S,G) 4466 periodic messages to the appropriate RPF' neighbor, i.e., the RPF 4467 neighbor as modified by the assert process. They are not always 4468 sent to the RPF neighbor as indicated by the MRIB. Normal 4469 suppression and override rules apply. 4471 Rationale: By sending the periodic and triggered Join messages to 4472 the RPF' neighbor instead of to the RPF neighbor, the downstream 4473 router avoids re-triggering the Assert process with every Join. A 4474 side effect of sending Joins to the Assert winner is that traffic 4475 will not switch back to the "normal" RPF neighbor until the Assert 4476 times out. This will not happen until data stops flowing, if item 4477 8 below is implemented. 4479 2. Behavior: The assert winner for (*,G) acts as the local DR for 4480 (*,G) on behalf of IGMP/MLD members. 4482 Rationale: This is required to allow a single router to merge PIM 4483 and IGMP/MLD joins and leaves. Without this, overrides don't work. 4485 3. Behavior: The assert winner for (S,G) acts as the local DR for 4486 (S,G) on behalf of IGMPv3 members. 4488 Rationale: Same rationale as for 2. 4490 4. Behavior: (S,G) and (*,G) prune overrides are sent to the RPF' 4491 neighbor and not to the regular RPF neighbor. 4493 Rationale: Same as for 1. 4495 5. Behavior: An (S,G,rpt) prune override is not sent (at all) if 4496 RPF'(S,G,rpt) != RPF'(*,G). 4498 Rationale: This avoids keeping state alive on the (S,G) tree when 4499 only (*,G) downstream members are left. Also, it avoids sending 4500 (S,G,rpt) joins to a router that is not on the (*,G) tree. This 4501 behavior might be confusing although this specification does 4502 indicate that such a join should be dropped. 4504 6. Behavior: An assert loser that receives a Join(S,G) with an 4505 Upstream Neighbor Address that is one of its addresses on that 4506 interface cancels the (S,G) Assert Timer. 4508 Rationale: This is necessary in order to have rapid convergence in 4509 the event that the downstream router that initially sent a join to 4510 the prior Assert winner has undergone a topology change. 4512 7. Behavior: An assert loser that receives a Join(*,G) or a 4513 Join(*,*,RP(G)) with an Upstream Neighbor Address that is one of 4514 its addresses on that interface cancels the (*,G) Assert Timer and 4515 all (S,G) assert timers that do not have corresponding 4516 Prune(S,G,rpt) messages in the compound Join/Prune message. 4518 Rationale: Same as 6. 4520 8. Behavior: An assert winner for (*,G) or (S,G) sends a canceling 4521 assert when it is about to stop forwarding on a (*,G) or an (S,G) 4522 entry. This behavior does not apply to (S,G,rpt). 4524 Rationale: This allows switching back to the shared tree after the 4525 last SPT router on the LAN leaves. Doing this prevents downstream 4526 routers on the shared tree from keeping SPT state alive. 4528 9. Behavior: Re-send the assert messages before timing out an assert. 4529 (This behavior is optional.) 4531 Rationale: This prevents the periodic duplicates that would 4532 otherwise occur each time that an assert times out and is then re- 4533 established. 4535 10. Behavior: When RPF'(S,G,rpt) changes to be the same as RPF'(*,G) we 4536 need to trigger a Join(S,G,rpt) to RPF'(*,G). 4538 Rationale: This allows switching back to the RPT after the last SPT 4539 member leaves. 4541 4.7. PIM Bootstrap and RP Discovery 4543 For correct operation, every PIM router within a PIM domain must be able 4544 to map a particular multicast group address to the same RP. If this is 4545 not the case then black holes may appear, where some receivers in the 4546 domain cannot receive some groups. A domain in this context is a 4547 contiguous set of routers that all implement PIM and are configured to | 4548 operate within a common boundary. 4550 A notable exception to this is where a PIM domain is broken up into 4551 multiple administrative scope regions - these are regions where a border 4552 has been configured so that a range of multicast groups will not be 4553 forwarded across that border. For more information on Administratively 4554 Scoped IP Multicast, see RFC 2365. The modified criteria for admin- 4555 scoped regions are that the region is convex with respect to forwarding 4556 based on the MRIB, and that all PIM routers within the scope region map 4557 scoped groups to the same RP within that region. 4559 This specification does not mandate the use of a single mechanism to 4560 provide routers with the information to perform the group-to-RP mapping. 4561 Currently three mechanisms are possible, and all three have associated 4562 problems: 4564 Static Configuration 4565 A PIM router MUST support the static configuration of group-to-RP 4566 mappings. Such a mechanism is not robust to failures, but does at 4567 least provide a basic interoperability mechanism. | 4569 Embeded-RP | 4570 Embeded-RP defines an address allocation policy in which the | 4571 address of the Rendezvous Point (RP) is encoded in an IPv6 | 4572 multicast group address [15]. 4574 Cisco's Auto-RP 4575 Auto-RP uses a PIM Dense-Mode multicast group to announce group-to- 4576 RP mappings from a central location. This mechanism is not useful 4577 if PIM Dense-Mode is not being run in parallel with PIM Sparse- 4578 Mode, and was only intended for use with PIM Sparse-Mode Version 1. 4579 No standard specification currently exists. 4581 BootStrap Router (BSR) 4582 RFC 2362 specifies a bootstrap mechanism based around the automatic 4583 election of a bootstrap router (BSR). Any router in the domain 4584 that is configured to be a possible RP reports its candidacy to the 4585 BSR, and then a domain-wide flooding mechanism distributes the 4586 BSR's chosen set of RPs throughout the domain. As specified in RFC 4587 2362, BSR is flawed in its handling of admin-scoped regions that 4588 are smaller than a PIM domain, but the mechanism does work for 4589 global-scoped groups. 4591 As far as PIM-SM is concerned, the only important requirement is that 4592 all routers in the domain (or admin scope zone for scoped regions) 4593 receive the same set of group-range-to-RP mappings. This may be 4594 achieved through the use of any of these mechanisms, or through 4595 alternative mechanisms not currently specified. 4597 It must be operationally ensured that any RP address configured, learned | 4598 or advertised is reachable from all routers in the PIM domain. 4600 4.7.1. Group-to-RP Mapping 4602 Using one of the mechanisms described above, a PIM router receives one 4603 or more possible group-range-to-RP mappings. Each mapping specifies a 4604 range of multicast groups (expressed as a group and mask) and the RP to 4605 which such groups should be mapped. Each mapping may also have an 4606 associated priority. It is possible to receive multiple mappings all of 4607 which might match the same multicast group - this is the common case 4608 with BSR. The algorithm for performing the group-to-RP mapping is as 4609 follows: 4611 1 Perform longest match on group-range to obtain a list of RPs. 4613 2 From this list of matching RPs, find the one with highest priority. 4614 Eliminate any RPs from the list that have lower priorities. 4616 3 If only one RP remains in the list, use that RP. 4618 4 If multiple RPs are in the list, use the PIM hash function to 4619 choose one. 4621 Thus if two or more group-range-to-RP mappings cover a particular group, 4622 the one with the longest mask is the mapping to use. If the mappings 4623 have the same mask length, then the one with the highest priority is 4624 chosen. If there is more than one matching entry with the same longest 4625 mask and the priorities are identical, then a hash function (see Section 4626 4.7.2) is applied to choose the RP. 4628 This algorithm is invoked by a DR when it needs to determine an RP for a 4629 given group, e.g. upon reception of a packet or IGMP/MLD membership 4630 indication for a group for which the DR does not know the RP. It is 4631 invoked by any router that has (*,*,RP) state when a packet is received 4632 for which there is no corresponding (S,G) or (*,G) entry. Furthermore, 4633 the mapping function is invoked by all routers upon receiving a (*,G) or 4634 (*,*,RP) Join/Prune message. 4636 Note that if the set of possible group-range-to-RP mappings changes, 4637 each router will need to check whether any existing groups are affected. 4638 This may, for example, cause a DR or acting DR to re-join a group, or 4639 cause it to re-start register encapsulation to the new RP. 4641 Implementation note: the bootstrap mechanism described in RFC 4642 2362 omitted step (1) above. However of the implementations 4643 we are aware of, approximately half performed step (1) anyway. 4644 It should be noted that implementations of BSR that omit step 4645 1 will not correctly interoperate with implementations of this 4646 specification when used with the BSR mechanism described in 4647 [11]. 4649 4.7.2. Hash Function 4651 The hash function is used by all routers within a domain, to map a group 4652 to one of the RPs from the matching set of group-range-to-RP mappings 4653 (this set all have the same longest mask length and same highest 4654 priority). The algorithm takes as input the group address, and the 4655 addresses of the candidate RPs from the mappings, and gives as output 4656 one RP address to be used. 4658 The protocol requires that all routers hash to the same RP within a 4659 domain (except for transients). The following hash function must be used 4660 in each router: 4662 1 For RP addresses in the matching group-range-to-RP mappings, 4663 compute a value: 4665 Value(G,M,C(i))= 4666 (1103515245 * ((1103515245 * (G&M)+12345) XOR C(i)) + 12345) mod 2^31 4668 where C(i) is the RP address and M is a hash-mask. If BSR is being 4669 used, the hash-mask is given in the Bootstrap messages. If BSR is 4670 not being used, the alternative mechanism that supplies the group- 4671 range-to-RP mappings may supply the value, or else it defaults to a 4672 mask with the most significant 30 bits being one for IPv4 and the 4673 most significant 126 bits being one for IPv6. The hash-mask allows 4674 a small number of consecutive groups (e.g., 4) to always hash to 4675 the same RP. For instance, hierarchically-encoded data can be sent 4676 on consecutive group addresses to get the same delay and fate- 4677 sharing characteristics. 4679 For address families other than IPv4, a 32-bit digest to be used as 4680 C(i) and G must first be derived from the actual RP or group 4681 address. Such a digest method must be used consistently throughout 4682 the PIM domain. For IPv6 addresses, we recommend using the 4683 equivalent IPv4 address for an IPv4-compatible address, and the 4684 exclusive-or of each 32-bit segment of the address for all other 4685 IPv6 addresses. For example, the digest of the IPv6 address 4686 3ffe:b00:c18:1::10 would be computed as 0x3ffe0b00 ^ 0x0c180001 ^ 4687 0x00000000 ^ 0x00000010, where ^ represents the exclusive-or 4688 operation. 4690 2 The candidate RP with the highest resulting hash value is then the 4691 RP chosen by this Hash Function. If more than one RP has the same 4692 highest hash value, the RP with the highest IP address is chosen. 4694 4.8. Source-Specific Multicast 4696 The Source-Specific Multicast (SSM) service model [5] can be implemented 4697 with a strict subset of the PIM-SM protocol mechanisms. Both regular IP 4698 Multicast and SSM semantics can coexist on a single router and both can 4699 be implemented using the PIM-SM protocol. A range of multicast | 4700 addresses, currently 232.0.0.0/8 in IPv4 and FF3x::/32 for IPv6, is | 4701 reserved for SSM, and the choice of semantics is determined by the 4702 multicast group address in both data packets and PIM messages. 4704 4.8.1. Protocol Modifications for SSM destination addresses 4706 The following rules override the normal PIM-SM behavior for a multicast 4707 address G in the SSM range: 4709 o A router MUST NOT send a (*,G) Join/Prune message for any reason. 4711 o A router MUST NOT send an (S,G,rpt) Join/Prune message for any reason. 4713 o A router MUST NOT send a Register message for any packet that is 4714 destined to an SSM address. 4716 o A router MUST NOT forward packets based on (*,G) or (S,G,rpt) state. 4717 The (*,G) and (S,G,rpt) -related state summarization macros are NULL 4718 for any SSM address, for the purposes of packet forwarding. 4720 o A router acting as an RP MUST NOT forward any Register-encapsulated 4721 packet that has an SSM destination address. 4723 The last two rules are present to deal with "legacy" routers unaware of 4724 SSM that may be sending (*,G) and (S,G,rpt) Join/Prunes, or Register 4725 messages for SSM destination addresses. 4727 Additionally: 4729 o A router MAY be configured to advertise itself as a Candidate RP for 4730 an SSM address. If so, it SHOULD respond with a Register-Stop message 4731 to any Register message containing a packet destined for an SSM 4732 address. 4734 o A router MAY optimize out the creation and maintenance of (S,G,rpt) 4735 and (*,G) state for SSM destination addresses -- this state is not 4736 needed for SSM packets. 4738 4.8.2. PIM-SSM-only Routers 4740 An implementor may choose to implement only the subset of PIM Sparse- 4741 Mode that provides SSM forwarding semantics. 4743 A PIM-SSM-only router MUST implement the following portions of this 4744 specification: 4746 o Upstream (S,G) state machine (Section 4.5.7) 4748 o Downstream (S,G) state machine (Section 4.5.3) 4750 o (S,G) Assert state machine (Section 4.6.1) 4752 o Hello messages, neighbor discovery and DR election (Section 4.3) 4754 o Packet forwarding rules (Section 4.2) 4755 A PIM-SSM-only router does not need to implement the following protocol 4756 elements: 4758 o Register state machine (Section 4.4) 4760 o (*,G), (S,G,rpt) and (*,*,RP) Downstream state machines (Sections 4761 4.5.2, 4.5.4, and 4.5.1) 4763 o (*,G), (S,G,rpt), and (*,*,RP) Upstream state machines (Sections 4764 4.5.6, 4.5.8, and 4.5.5) 4766 o (*,G) Assert state machine (Section 4.6.2) 4768 o Bootstrap RP Election (Section 4.7) 4770 o Keepalive Timer 4772 o SptBit (Section 4.2.2) 4774 The Keepalive Timer should be treated as always running and SptBit 4775 should be treated as being always set for an SSM address. Additionally, 4776 the Packet forwarding rules of Section 4.2 can be simplified in a PIM- 4777 SSM-only router: 4779 if( iif == RPF_interface(S) AND UpstreamJPState(S,G) == Joined ) { 4780 oiflist = inherited_olist(S,G) 4781 } else if( iif is in inherited_olist(S,G) ) { 4782 send Assert(S,G) on iif 4783 } 4785 oiflist = oiflist (-) iif 4786 forward packet on all interfaces in oiflist 4788 This is nothing more than the reduction of the normal PIM-SM forwarding 4789 rule, with all (S,G,rpt) and (*,G) clauses replaced with NULL. 4791 4.9. PIM Packet Formats 4793 This section describes the details of the packet formats for PIM control 4794 messages. 4796 All PIM control messages have IP protocol number 103. 4798 PIM messages are either unicast (e.g. Registers and Register-Stop), or 4799 multicast with TTL 1 to the `ALL-PIM-ROUTERS' group (e.g. Join/Prune, 4800 Asserts, etc.). The source address used for unicast messages is a 4801 domain-wide reachable address; the source address used for multicast 4802 messages is the link-local address of the interface on which the message 4803 is being sent. 4805 The IPv4 `ALL-PIM-ROUTERS' group is `224.0.0.13'. The IPv6 `ALL-PIM- 4806 ROUTERS' group is `ff02::d'. 4808 The PIM header common to all PIM messages is: 4810 0 1 2 3 4811 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 4812 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4813 |PIM Ver| Type | Reserved | Checksum | 4814 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4816 PIM Ver 4817 PIM Version number is 2. 4819 Type Types for specific PIM messages. PIM Types are: 4821 Message Type Destination 4822 Mes--------------------------------------------------------------------------- 4823 0 = Hello Multicast to ALL-PIM-ROUTERS 4824 1 = Register Unicast to RP 4825 2 = Register-Stop Unicast to source of Register packet 4826 3 = Join/Prune Multicast to ALL-PIM-ROUTERS 4827 4 = Bootstrap Multicast to ALL-PIM-ROUTERS 4828 5 = Assert Multicast to ALL-PIM-ROUTERS 4829 6 = Graft (used in PIM-DM only) Multicast to ALL-PIM-ROUTERS 4830 7 = Graft-Ack (used in PIM-DM only) Unicast to source of Graft packet 4831 8 = Candidate-RP-Advertisement Unicast to Domain's BSR 4833 Reserved 4834 Set to zero on transmission. Ignored upon receipt. 4836 Checksum 4837 The checksum is a standard IP checksum, i.e. the 16-bit one's 4838 complement of the one's complement sum of the entire PIM message, 4839 excluding the "Multicast data packet" section of the Register 4840 message. For computing the checksum, the checksum field is zeroed. | 4841 If the packet's length is not an integral number of 16-bit words, | 4842 the packet is padded with a trailing byte of zero before performing | 4843 the checksum. 4845 For IPv6, the checksum also includes the IPv6 "pseudo-header", as 4846 specified in RFC 2460, Section 8.1 [4]. This "pseudo-header" is 4847 prepended to the PIM header for the purposes of calculating the 4848 checksum. The "Upper-Layer Packet Length" in the pseudo-header is 4849 set to the length of the PIM message, except in Register messages | 4850 where it is set to the length of the PIM register header (8). The 4851 Next Header value used in the pseudo-header is 103. 4853 If a message is received with an unrecognized PIM Ver or Type field or a | 4854 message's destination does not correspond to the table above, it MUST be 4855 discarded and an error message SHOULD be logged to the administrator in 4856 a rate limited manner. 4858 4.9.1. Encoded Source and Group Address Formats 4860 Encoded-Unicast address 4862 An Encoded-Unicast address takes the following format: 4864 0 1 2 3 4865 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 4866 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4867 | Addr Family | Encoding Type | Unicast Address 4868 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+... 4870 Addr Family 4871 The PIM address family of the `Unicast Address' field of this 4872 address. 4874 Values of 0-127 are as assigned by the IANA for Internet Address 4875 Families in [6]. Values 128-250 are reserved to be assigned by the 4876 IANA for PIM-specific Address Families. Values 251 though 255 are 4877 designated for private use. As there is no assignment authority 4878 for this space, collisions should be expected. 4880 Encoding Type 4881 The type of encoding used within a specific Address Family. The 4882 value `0' is reserved for this field, and represents the native 4883 encoding of the Address Family. 4885 Unicast Address 4886 The unicast address as represented by the given Address Family and 4887 Encoding Type. 4889 Encoded-Group address 4891 Encoded-Group addresses take the following format: 4893 0 1 2 3 4894 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 4895 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4896 | Addr Family | Encoding Type |B| Reserved |Z| Mask Len | 4897 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4898 | Group multicast Address 4899 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+... 4901 Addr Family 4902 described above. 4904 Encoding Type 4905 described above. 4907 [B]idirectional PIM 4908 indicates the group range should use Bidirectional PIM [12]. For 4909 PIM-SM defined in this specification, this bit MUST be zero. 4911 Reserved 4912 Transmitted as zero. Ignored upon receipt. 4914 Admin Scope [Z]one 4915 indicates the group range is an admin scope zone. This is used in 4916 the Bootstrap Router Mechanism [11] only. For all other purposes, 4917 this bit is set to zero and ignored on receipt. 4919 Mask Len 4920 The Mask length field is 8 bits. The value is the number of 4921 contiguous one bits left justified used as a mask which, combined 4922 with the group address, describes a range of groups. It is less 4923 than or equal to the address length in bits for the given Address 4924 Family and Encoding Type. If the message is sent for a single group 4925 then the Mask length must equal the address length in bits for the 4926 given Address Family and Encoding Type. (e.g. 32 for IPv4 native 4927 encoding, 128 for IPv6 native encoding). 4929 Group multicast Address 4930 Contains the group address. 4932 Encoded-Source address 4934 Encoded-Source address takes the following format: 4936 0 1 2 3 4937 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 4938 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4939 | Addr Family | Encoding Type | Rsrvd |S|W|R| Mask Len | 4940 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4941 | Source Address 4942 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-... 4944 Addr Family 4945 described above. 4947 Encoding Type 4948 described above. 4950 Reserved 4951 Transmitted as zero, ignored on receipt. 4953 S The Sparse bit is a 1 bit value, set to 1 for PIM-SM. It is used 4954 for PIM version 1 compatibility. 4956 W The WC (or WildCard) bit is a 1 bit value for use with PIM 4957 Join/Prune messages (see Section 4.9.5.1 ). 4959 R The RPT (or Rendezvous Point Tree) bit is a 1 bit value for use 4960 with PIM Join/Prune messages (see Section 4.9.5.1 ). If the WC bit 4961 is 1, the RPT bit MUST be 1. 4963 Mask Len 4964 The mask length field is 8 bits. The value is the number of 4965 contiguous one bits left justified used as a mask which, combined 4966 with the Source Address, describes a source subnet. The mask length 4967 MUST be equal to the mask length in bits for the given Address 4968 Family and Encoding Type (32 for IPv4 native and 128 for IPv6 4969 native). A router SHOULD ignore any messages received with any 4970 other mask length. 4972 Source Address 4973 The source address. 4975 4.9.2. Hello Message Format 4977 It is sent periodically by routers on all interfaces. 4979 0 1 2 3 4980 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 4981 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4982 |PIM Ver| Type | Reserved | Checksum | 4983 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4984 | OptionType | OptionLength | 4985 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4986 | OptionValue | 4987 | ... | 4988 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4989 | . | 4990 | . | 4991 | . | 4992 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4993 | OptionType | OptionLength | 4994 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4995 | OptionValue | 4996 | ... | 4997 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4999 PIM Version, Type, Reserved, Checksum 5000 Described in Section 4.9. 5002 OptionType 5003 The type of the option given in the following OptionValue field. 5005 OptionLength 5006 The length of the OptionValue field in bytes. 5008 OptionValue 5009 A variable length field, carrying the value of the option. 5011 The Option fields may contain the following values: 5013 o OptionType 1: Holdtime 5015 0 1 2 3 5016 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 5017 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5018 | Type = 1 | Length = 2 | 5019 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5020 | Holdtime | 5021 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5023 Holdtime is the amount of time a receiver must keep the neighbor 5024 reachable, in seconds. If the Holdtime is set to `0xffff', the 5025 receiver of this message never times out the neighbor. This may 5026 be used with dial-on-demand links, to avoid keeping the link up 5027 with periodic Hello messages. 5029 Hello messages with a Holdtime value set to `0' are also sent by 5030 a router on an interface about to go down or changing IP address 5031 (see Section 4.3.1). These are effectively goodbye messages and 5032 the receiving routers should immediately time out the neighbor 5033 information for the sender. 5035 o OptionType 2: LAN Prune Delay 5037 0 1 2 3 5038 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 5039 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5040 | Type = 2 | Length = 4 | 5041 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5042 |T| Propagation_Delay | Override_Interval | | 5043 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5045 The LAN Prune Delay option is used to tune the prune propagation 5046 delay on multi-access LANs. The T bit specifies the ability of 5047 the sending router to disable joins suppression. | 5048 Propagation_Delay and Override_Interval are time intervals in | 5049 units of milliseconds. A router originating a LAN Prune Delay | 5050 option on interface I sets the Propagation_Delay field to the | 5051 configured value of Propagation_Delay(I) and the value of the | 5052 Override_Interval field to the value of Override_Interval(I). On | 5053 a receiving router the values of the fields are used to tune the | 5054 value of the Effective_Override_Interval(I) and its derived timer | 5055 values. Section 4.3.3 describes how these values affect the 5056 behavior of a router. 5058 o OptionType 3 to 16: reserved to be defined in future versions of 5059 this document. 5061 o OptionType 18: deprecated and should not be used. 5063 o OptionType 19: DR Priority 5065 0 1 2 3 5066 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 5067 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5068 | Type = 19 | Length = 4 | 5069 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5070 | DR Priority | 5071 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5073 DR Priority is a 32-bit unsigned number and should be considered 5074 in the DR election as described in Section 4.3.2. 5076 o OptionType 20: Generation ID 5078 0 1 2 3 5079 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 5080 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5081 | Type = 20 | Length = 4 | 5082 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5083 | Generation ID | 5084 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5086 Generation ID is a random 32-bit value for the interface on which 5087 the Hello message is sent. The Generation ID is regenerated 5088 whenever PIM forwarding is started or restarted on the interface. 5090 o OptionType 24: Address List 5092 0 1 2 3 5093 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 5094 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5095 | Type = 24 | Length = | 5096 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5097 | Secondary Address 1 (Encoded-Unicast format) | 5098 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5099 ... 5100 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5101 | Secondary Address N (Encoded-Unicast format) | 5102 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5104 The contents of the Address List Hello option are described in 5105 Section 4.3.4. All addresses within a single Address List must 5106 belong to the same address family. 5108 OptionTypes 17 thru 65000 are assigned by the IANA. OptionTypes 5109 65001 through 65535 are reserved for Private Use, as defined in 5110 [8]. 5111 Unknown options may be ignored. The "Holdtime" option MUST be 5112 implemented; the "DR Priority" and "Generation ID" options SHOULD | 5113 be implemented. The "Address List" option MUST be implemented for | 5114 IPv6. 5116 4.9.3. Register Message Format 5118 A Register message is sent by the DR or a PMBR to the RP when a 5119 multicast packet needs to be transmitted on the RP-tree. The IP source 5120 address is set to the address of the DR, the destination address to the 5121 RP's address. The IP TTL of the PIM packet is the system's normal 5122 unicast TTL. 5124 0 1 2 3 5125 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 5126 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5127 |PIM Ver| Type | Reserved | Checksum | 5128 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5129 |B|N| Reserved2 | 5130 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5131 | | 5132 . Multicast data packet . 5133 | | 5134 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5136 PIM Version, Type, Reserved, Checksum 5137 Described in Section 4.9. Note that in order to reduce 5138 encapsulation overhead, the checksum for Registers is done only on 5139 first 8 bytes of the packet, including the PIM header and the next 5140 4 bytes, excluding the data packet portion. For interoperability 5141 reasons, a message carrying a checksum calculated over the entire 5142 PIM Register message should also be accepted. When calculating the 5143 checksum, the IPv6 pseudoheader "Upper-Layer Packet Length" is set 5144 to 8. 5146 B The Border bit. If the router is a DR for a source that it is 5147 directly connected to, it sets the B bit to 0. If the router is a 5148 PMBR for a source in a directly connected cloud, it sets the B bit 5149 to 1. 5151 N The Null-Register bit. Set to 1 by a DR that is probing the RP 5152 before expiring its local Register-Suppression Timer. Set to 0 5153 otherwise. 5155 Reserved2 5156 Transmitted as zero, ignored on receipt. 5158 Multicast data packet 5159 The original packet sent by the source. This packet must be of the 5160 same address family as the encapsulating PIM packet, e.g. an IPv6 5161 data packet must be encapsulated in an IPv6 PIM packet. Note that 5162 the TTL of the original packet is decremented before encapsulation, 5163 just like any other packet that is forwarded. In addition, the RP 5164 decrements the TTL after decapsulating, before forwarding the 5165 packet down the shared tree. 5167 For (S,G) Null-Registers, the Multicast data packet portion 5168 contains a dummy IP header with S as the source address, G as the 5169 destination address. When generating an IPv4 Null-Register 5170 message, the fields in the dummy IPv4 header SHOULD be filled in 5171 according to the following table. Other IPv4 header fields may 5172 contain any value that is valid for that field. 5174 Field Value 5175 --------------------------------------- 5176 IP Version 4 5177 Header Length 5 5178 Checksum Header checksum 5179 Fragmentation offset 0 5180 More Fragments 0 5181 Total Length 20 5182 IP Protocol 103 (PIM) 5184 On receipt of an (S,G) Null-Register, if the Header Checksum field 5185 is non-zero, the recipient SHOULD check the checksum and discard 5186 null registers that have a bad checksum. The recipient SHOULD NOT 5187 check the value of any individual fields; a correct IP header 5188 checksum is sufficient. If the Header Checksum field is zero, the 5189 recipient MUST NOT check the checksum. 5191 With IPv6, an implementation generates a dummy IP header followed 5192 by a dummy PIM header with values according to the following table 5193 in addition to the source and group. Other IPv6 header fields may 5194 contain any value that is valid for that field. 5196 Header Field Value 5197 -------------------------------------- 5198 IP Version 6 5199 Next Header 103 (PIM) 5200 Length 4 5201 PIM Version 0 5202 PIM Type 0 5203 PIM Reserved 0 5204 PIM Checksum PIM checksum including 5205 IPv6 "pseudo-header"; 5206 see Section 4.9 5208 On receipt of an IPv6 (S,G) Null-Register, if the dummy PIM header 5209 is present, the recipient SHOULD check the checksum and discard | 5210 Null-Registers that have a bad checksum. 5212 4.9.4. Register-Stop Message Format 5214 A Register-Stop is unicast from the RP to the sender of the Register 5215 message. The IP source address is the address to which the register was 5216 addressed. The IP destination address is the source address of the 5217 register message. 5219 0 1 2 3 5220 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 5221 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5222 |PIM Ver| Type | Reserved | Checksum | 5223 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5224 | Group Address (Encoded-Group format) | 5225 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5226 | Source Address (Encoded-Unicast format) | 5227 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5229 PIM Version, Type, Reserved, Checksum 5230 Described in Section 4.9. 5232 Group Address 5233 The group address from the multicast data packet in the Register. 5234 Format described in Section 4.9.1. Note that for Register-Stops the 5235 Mask Len field contains the full address length * 8 (e.g. 32 for 5236 IPv4 native encoding), if the message is sent for a single group. 5238 Source Address 5239 The host address of the source from the multicast data packet in 5240 the register. The format for this address is given in the Encoded- 5241 Unicast address in Section 4.9.1. A special wild card value 5242 consisting of an address field of all zeroes can be used to 5243 indicate any source. 5245 4.9.5. Join/Prune Message Format 5247 A Join/Prune message is sent by routers towards upstream sources and 5248 RPs. Joins are sent to build shared trees (RP trees) or source trees 5249 (SPT). Prunes are sent to prune source trees when members leave groups 5250 as well as sources that do not use the shared tree. 5252 0 1 2 3 5253 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 5254 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5255 |PIM Ver| Type | Reserved | Checksum | 5256 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5257 | Upstream Neighbor Address (Encoded-Unicast format) | 5258 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5259 | Reserved | Num groups | Holdtime | 5260 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5261 | Multicast Group Address 1 (Encoded-Group format) | 5262 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5263 | Number of Joined Sources | Number of Pruned Sources | 5264 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5265 | Joined Source Address 1 (Encoded-Source format) | 5266 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5267 | . | 5268 | . | 5269 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5270 | Joined Source Address n (Encoded-Source format) | 5271 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5272 | Pruned Source Address 1 (Encoded-Source format) | 5273 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5274 | . | 5275 | . | 5276 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5277 | Pruned Source Address n (Encoded-Source format) | 5278 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5279 | . | 5280 | . | 5281 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5282 | Multicast Group Address m (Encoded-Group format) | 5283 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5284 | Number of Joined Sources | Number of Pruned Sources | 5285 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5286 | Joined Source Address 1 (Encoded-Source format) | 5287 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5288 | . | 5289 | . | 5290 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5291 | Joined Source Address n (Encoded-Source format) | 5292 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5293 | Pruned Source Address 1 (Encoded-Source format) | 5294 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5295 | . | 5296 | . | 5297 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5298 | Pruned Source Address n (Encoded-Source format) | 5299 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5300 PIM Version, Type, Reserved, Checksum 5301 Described in Section 4.9. 5303 Unicast Upstream Neighbor Address 5304 The address of the upstream neighbor that is the target of the 5305 message. The format for this address is given in the Encoded- 5306 Unicast address in Section 4.9.1. For IPv6 the source address used 5307 for multicast messages is the link-local address of the interface 5308 on which the message is being sent. For IPv4, the source address 5309 is the primary address associated with that interface. 5311 Reserved 5312 Transmitted as zero, ignored on receipt. 5314 Holdtime 5315 The amount of time a receiver must keep the Join/Prune state alive, 5316 in seconds. If the Holdtime is set to `0xffff', the receiver of 5317 this message should hold the state until canceled by the 5318 appropriate canceling Join/Prune message, or timed out according to 5319 local policy. This may be used with dial-on-demand links, to avoid 5320 keeping the link up with periodic Join/Prune messages. 5322 Note that the HoldTime must be larger than the 5323 J/P_Override_Interval(I). 5325 Number of Groups 5326 The number of multicast group sets contained in the message. 5328 Multicast group address 5329 For format description see Section 4.9.1. 5331 Number of Joined Sources 5332 Number of join source addresses listed for a given group. 5334 Join Source Address 1 .. n 5335 This list contains the sources that the sending router will forward 5336 multicast datagrams for if received on the interface this message 5337 is sent on. 5339 See Encoded-Source-Address format in Section 4.9.1. 5341 Number of Pruned Sources 5342 Number of prune source addresses listed for a group. 5344 Prune Source Address 1 .. n 5345 This list contains the sources that the sending router does not 5346 want to forward multicast datagrams for when received on the 5347 interface this message is sent on. 5349 Within one PIM Join/Prune message, all the Multicast Group Addresses, 5350 Joined Source addresses and Pruned Source addresses MUST be of the same 5351 address family. It is NOT PERMITTED to mix IPv4 and IPv6 addresses 5352 within the same message. In addition, the address family of the fields 5353 in the message SHOULD be the same as the IP source and destination 5354 addresses of the packet. This permits maximum implementation 5355 flexibility for dual-stack IPv4/IPv6 routers. If a router receives a 5356 message with mixed family addresses, it SHOULD only process the 5357 addresses which are of the same family as the unicast upstream neighbor 5358 address. 5360 4.9.5.1. Group Set Source List Rules 5362 As described above, Join / Prune messages are composed of one or more 5363 group sets. Each set contains two source lists, the Join Sources and the 5364 Prune Sources. This section describes the different types of group sets 5365 and source list entries that can exist in a Join / Prune message. 5367 There are two valid group set types: 5369 Wildcard Group Set 5370 The wildcard group set is represented by the entire multicast range 5371 - the beginning of the multicast address range in the group address 5372 field and the prefix length of the multicast address range in the 5373 mask length field of the Multicast Group Address, i.e., 5374 `224.0.0.0/4' for IPv4 or `ff00::/8' for IPv6. Each wildcard group 5375 set may contain one or more (*,*,RP) source list entries in either 5376 the Join or Prune lists. 5378 A (*,*,RP) source list entry may only exist in a wildcard group 5379 set. When added to a Join source list, this type of source entry 5380 expresses the router's interest in receiving traffic for all groups 5381 mapping to the specified RP. When added to a Prune source list a 5382 (*,*,RP) entry expresses the router's interest to stop receiving 5383 such traffic. Note that as indicated by the Join/Prune state 5384 machines, such a Join or Prune will NOT override Join/Prune state 5385 created using a Group-Specific Set (see below). 5387 (*,*,RP) source list entries have the Source-Address set to the 5388 address of the RP, the Source-Address Mask-Len set to the full 5389 length of the IP address and both the WC and RPT bits of the 5390 Source-Address set to 1. 5392 Group Specific Set 5393 A Group Specific Set is represented by a valid IP multicast address 5394 in the group address field and the full length of the IP address in 5395 the mask length field of the Multicast Group Address. Each group 5396 specific set may contain (*,G), (S,G,rpt) and (S,G) source list 5397 entries in the Join or Prune lists. 5399 (*,G) 5400 The (*,G) source list entry is used in Join / Prune messages 5401 sent towards the RP for the specified group. It expresses 5402 interest (or lack of) in receiving traffic sent to the group 5403 through the Rendezvous-Point shared tree. There may only be 5404 one such entry in both the Join and Prune lists of a group 5405 specific set. 5407 (*,G) source list entries have the Source-Address set to the 5408 address of the RP for group G, the Source-Address Mask-Len set 5409 to the full length of the IP address and have both the WC and 5410 RPT bits of the Encoded-Source-Address set. 5412 (S,G,rpt) 5413 The (S,G,rpt) source list entry is used in Join / Prune 5414 messages sent towards the RP for the specified group. It 5415 expresses interest (or lack of) in receiving traffic through 5416 the shared tree sent by the specified source to this group. 5417 For each source address the entry may exist in only one of the 5418 Join and Prune source lists of a group specific set but not 5419 both. 5421 (S,G,rpt) source list entries have the Source-Address set to 5422 the address of the source S, the Source-Address Mask-Len set 5423 to the full length of the IP address and have the WC bit clear 5424 and the RPT bit set in the Encoded-Source-Address. 5426 (S,G) 5427 The (S,G) source list entry is used in Join / Prune messages 5428 sent towards the specified source. It expresses interest (or 5429 lack of) in receiving traffic through the shortest path tree 5430 sent by the source to the specified group. For each source 5431 address the entry may exist in only one of the Join and Prune 5432 source lists of a group specific set but not both. 5434 (S,G) source list entries have the Source-Address set to the 5435 address of the source S, the Source-Address Mask-Len set to 5436 the full length of the IP address and have both the WC and RPT 5437 bits of the Encoded-Source-Address cleared. 5439 The rules described above are sufficient to prevent invalid combinations 5440 of source list entries in group-specific sets. There are however a 5441 number of combinations that have a valid interpretation but which are 5442 not generated by the protocol as described in this specification: 5444 o Combining a (*,G) Join and a (S,G,rpt) Join entry in the same message 5445 is redundant as the (*,G) entry covers the information provided by the 5446 (S,G,rpt) entry. 5448 o The same applies for a (*,G) Prunes and (S,G,rpt) Prunes. 5450 o The combination of a (*,G) Prune and a (S,G,rpt) Join is also not 5451 generated. (S,G,rpt) Joins are only sent when the router is receiving 5452 all traffic for a group on the shared tree and it wishes to indicate a 5453 change for the particular source. As a (*,G) prune indicates that the 5454 router no longer wishes to receive shared tree traffic, the (S,G,rpt) 5455 Join would be meaningless. 5457 o As Join / Prune messages are targeted to a single PIM neighbor, 5458 including both a (S,G) Join and a (S,G,rpt) Prune in the same message 5459 is redundant. The (S,G) Join informs the neighbor that the sender 5460 wishes to receive the particular source on the shortest path tree. It 5461 is therefore unnecessary for the router to say that it no longer 5462 wishes to receive it on the shared tree. 5464 o The combination of a (S,G) Prune and a (S,G,rpt) Join could possibly 5465 be used by a router to switch from receiving a particular source on 5466 the shortest-path tree back to receiving it on the shared tree 5467 (provided that the RPF neighbor for the shortest-path and shared trees 5468 is common). However Sparse-Mode PIM does not provide a mechanism for 5469 switching back to the shared tree. 5471 The rules are summarized in the tables below. 5473 +----------++------+-------+-----------+-----------+-------+-------+ 5474 | ||Join | Prune | Join | Prune | Join | Prune | 5475 | ||(*,G) | (*,G) | (S,G,rpt) | (S,G,rpt) | (S,G) | (S,G) | 5476 +----------++------+-------+-----------+-----------+-------+-------+ 5477 |Join ||- | no | ? | yes | yes | yes | 5478 |(*,G) || | | | | | | 5479 +----------++------+-------+-----------+-----------+-------+-------+ 5480 |Prune ||no | - | ? | ? | yes | yes | 5481 |(*,G) || | | | | | | 5482 +----------++------+-------+-----------+-----------+-------+-------+ 5483 |Join ||? | ? | - | no | yes | ? | 5484 |(S,G,rpt) || | | | | | | 5485 +----------++------+-------+-----------+-----------+-------+-------+ 5486 |Prune ||yes | ? | no | - | ? | yes | 5487 |(S,G,rpt) || | | | | | | 5488 +----------++------+-------+-----------+-----------+-------+-------+ 5489 |Join ||yes | yes | yes | ? | - | no | 5490 |(S,G) || | | | | | | 5491 +----------++------+-------+-----------+-----------+-------+-------+ 5492 |Prune ||yes | yes | yes | ? | no | - | 5493 |(S,G) || | | | | | | 5494 +----------++------+-------+-----------+-----------+-------+-------+ 5496 +---------------++--------------+----------------+------------+ 5497 | ||Join (*,*,RP) | Prune (*,*,RP) | all others | 5498 +---------------++--------------+----------------+------------+ 5499 |Join (*,*,RP) ||- | no | yes | 5500 +---------------++--------------+----------------+------------+ 5501 |Prune (*,*,RP) ||no | - | yes | 5502 +---------------++--------------+----------------+------------+ 5503 |all others ||yes | yes | see above | 5504 +---------------++--------------+----------------+------------+ 5506 yes Allowed and expected. 5508 no Combination is not allowed by the protocol and MUST NOT be 5509 generated by a router. A router MAY accept these messages but the 5510 result is undefined. An error message MAY be logged to the 5511 administrator in a rate limited manner. 5513 ? Combination not expected by the protocol, but well-defined. A 5514 router MAY accept it but SHOULD NOT generate it. 5516 The order of source list entries in a group set source list is not 5517 important, except where limited by the packet format itself. 5519 4.9.5.2. Group Set Fragmentation 5521 When building a Join / Prune for a particular neighbor, a router should 5522 try and include in the message as much of the information it needs to 5523 convey to the neighbor as possible. This implies adding one group set 5524 for each multicast group that has information pending transmission and 5525 within each set including all relevant source list entries. 5527 On a router with a large amount of multicast state the number of entries 5528 that must be included may result in packets that are larger than the 5529 maximum IP packet size. In most such cases the information may be split 5530 into multiple messages. 5532 There is an exception with group sets that contain a (*,G) Join source 5533 list entry. The group set expresses the router's interest in receiving 5534 all traffic for the specified group on the shared tree and it MUST 5535 include an (S,G,rpt) Prune source list entry for every source that the 5536 router does not wish to receive. This list of (S,G,rpt) Prune source- 5537 list entries MUST not be split in multiple messages. 5539 If only N (S,G,rpt) Prune entries fit into a maximum-sized Join / Prune 5540 message, but the router has more than N (S,G,rpt) Prunes to add, then 5541 the router MUST choose to include the first N (numerically smallest in 5542 network byte order) IP addresses. 5544 4.9.6. Assert Message Format 5546 The Assert message is used to resolve forwarder conflicts between 5547 routers on a link. It is sent when a multicast data packet is received 5548 on an interface that the router would normally forward that packet. 5549 Assert messages may also be sent in response to an Assert message from 5550 another router. 5552 0 1 2 3 5553 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 5554 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5555 |PIM Ver| Type | Reserved | Checksum | 5556 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5557 | Group Address (Encoded-Group format) | 5558 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5559 | Source Address (Encoded-Unicast format) | 5560 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5561 |R| Metric Preference | 5562 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5563 | Metric | 5564 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5566 PIM Version, Type, Reserved, Checksum 5567 Described in Section 4.9. 5569 Group Address 5570 The group address for which the router wishes to resolve the 5571 forwarding conflict. This is an Encoded-Group address, as 5572 specified in Section 4.9.1. 5574 Source Address 5575 Source address for which the router wishes to resolve the 5576 forwarding conflict. The source address MAY be set to zero for 5577 (*,G) asserts (see below). The format for this address is given in 5578 Encoded-Unicast-Address in Section 4.9.1. 5580 R RPT-bit is a 1 bit value. The RPT-bit is set to 1 for Assert(*,G) 5581 messages and 0 for Assert(S,G) messages. 5583 Metric Preference 5584 Preference value assigned to the unicast routing protocol that 5585 provided the route to the multicast source or Rendezvous-Point. 5587 Metric 5588 The unicast routing table metric associated with the route used to 5589 reach the multicast source or Rendezvous-Point. The metric is in 5590 units applicable to the unicast routing protocol used. 5592 Assert messages can be sent to resolve a forwarding conflict for all 5593 traffic to given group or for a specific source and group. 5595 Assert(S,G) 5596 Source specific asserts are sent by routers forwarding a specific | 5597 source on the shortest-path tree (SPTbit is TRUE). (S,G) Asserts | 5598 have the Group-Address field set to the group G and the Source- 5599 Address field set to the source S. The RPT-bit is set to 0, the 5600 Metric-Preference is set to MRIB.pref(S) and the Metric is set to 5601 MRIB.metric(S). 5603 Assert(*,G) 5604 Group specific asserts are sent by routers forwarding data for the 5605 group and source(s) under contention on the shared tree. (*,G) 5606 asserts have the Group-Address field set to the group G. For data 5607 triggered Asserts the Source-Address field MAY be set to the IP 5608 source address of the data packet that triggered the Assert and is 5609 set to zero otherwise. The RPT-bit is set to 1, the Metric- 5610 Preference is set to MRIB.pref(RP(G)) and the Metric is set to 5611 MRIB.metric(RP(G)). 5613 4.10. PIM Timers 5615 PIM-SM maintains the following timers, as discussed in Section 4.1. All 5616 timers are countdown timers - they are set to a value and count down to 5617 zero, at which point they typically trigger an action. Of course they 5618 can just as easily be implemented as count-up timers, where the absolute 5619 expiry time is stored and compared against a real-time clock, but the 5620 language in this specification assumes that they count downwards to 5621 zero. 5623 Global Timers 5625 Per interface (I): 5627 Hello Timer: HT(I) 5629 Per neighbor (N): 5631 Neighbor Liveness Timer: NLT(N,I) 5633 Per active RP (RP): 5635 (*,*,RP) Join Expiry Timer: ET(*,*,RP,I) 5637 (*,*,RP) Prune-Pending Timer: PPT(*,*,RP,I) 5639 Per Group (G): 5641 (*,G) Join Expiry Timer: ET(*,G,I) 5643 (*,G) Prune-Pending Timer: PPT(*,G,I) 5645 (*,G) Assert Timer: AT(*,G,I) 5647 Per Source (S): 5649 (S,G) Join Expiry Timer: ET(S,G,I) 5651 (S,G) Prune-Pending Timer: PPT(S,G,I) 5653 (S,G) Assert Timer: AT(S,G,I) 5655 (S,G,rpt) Prune Expiry Timer: ET(S,G,rpt,I) 5657 (S,G,rpt) Prune-Pending Timer: PPT(S,G,rpt,I) 5659 Per active RP (RP): 5661 (*,*,RP) Upstream Join Timer: JT(*,*,RP) 5663 Per Group (G): 5665 (*,G) Upstream Join Timer: JT(*,G) 5667 Per Source (S): 5669 (S,G) Upstream Join Timer: JT(S,G) 5671 (S,G) Keepalive Timer: KAT(S,G) 5673 (S,G,rpt) Upstream Override Timer: OT(S,G,rpt) 5675 At the DRs or relevant Assert Winners only: 5677 Per Source,Group pair (S,G): 5679 Register-Stop Timer: RST(S,G) 5681 4.11. Timer Values 5683 When timers are started or restarted, they are set to default values. 5684 This section summarizes those default values. 5686 Note that protocol events or configuration may change the default value 5687 of a timer on a specific interface. When timers are initialized in this 5688 document the value specific to the interface in context must be used. 5690 Some of the timers listed below (Prune-Pending, Upstream Join, Upstream 5691 Override) can be set to values which depend on the settings of the 5692 Propagation_Delay and Override_Interval of the corresponding interface. 5693 The default values for these are given below. 5695 Variable Name: Propagation_Delay(I) 5697 r+-------------------------------+---------------+-----------------------+ 5698 | Value Name | Value | Explanation | 5699 | 5700 +-------------------------------+---------------+-----------------------+ 5701 | Propagation_delay_default | 0.5 secs | Expected | 5702 | | | propagation delay | 5703 | | | over the local | 5704 | | | link. | 5705 | 5706 +-------------------------------+---------------+-----------------------+ 5708 The default value of the Propagation_delay_default is chosen to be | 5709 relatively large to provide compatibility with older PIM | 5710 implementations. 5712 Variable Name: Override_Interval(I) 5714 r+--------------------------+-----------------+--------------------------+ 5715 | Value Name | Value | Explanation | 5716 | 5717 +--------------------------+-----------------+--------------------------+ 5718 | t_override_default | 2.5 secs | Default delay | 5719 | | | interval over | 5720 | | | which to randomize | 5721 | | | when scheduling a | 5722 | | | delayed Join | 5723 | | | message. | 5724 | 5725 +--------------------------+-----------------+--------------------------+ 5727 Timer Name: Hello Timer (HT(I)) 5729 m+----------------------+---------+---------------------------------------+ 5730 |Value Name | Value | Explanation | 5731 | 5732 +----------------------+---------+---------------------------------------+ 5733 |Hello_Period | 30 secs | Periodic interval for Hello messages. | 5734 | 5735 +----------------------+---------+---------------------------------------+ 5736 |Triggered_Hello_Delay | 5 secs | Randomized interval for initial Hello | 5737 | | | message on bootup or triggered Hello | 5738 | | | message to a rebooting neighbor. | 5739 | 5740 +----------------------+---------+---------------------------------------+ 5741 At system power-up, the timer is initialized to rand(0, 5742 Triggered_Hello_Delay) to prevent synchronization. When a new or 5743 rebooting neighbor is detected, a responding Hello is sent within 5744 rand(0, Triggered_Hello_Delay). 5746 Timer Name: Neighbor Liveness Timer (NLT(N,I)) 5748 m+--------------------------+-----------------------+--------------------+ 5749 | Value Name | Value | Explanation | 5750 | 5751 +--------------------------+-----------------------+--------------------+ 5752 | Default_Hello_Holdtime | 3.5 * Hello_Period | Default holdtime | 5753 | | | to keep neighbor | 5754 | | | state alive | 5755 | 5756 +--------------------------+-----------------------+--------------------+ 5757 | Hello_Holdtime | from message | Holdtime from | 5758 | | | Hello Message | 5759 | | | Holdtime option. | 5760 | 5761 +--------------------------+-----------------------+--------------------+ 5763 The Holdtime in a Hello Message should be set to (3.5 * Hello_Period), 5764 giving a default value of 105 seconds. 5766 Timer Names: Expiry Timer (ET(*,*,RP,I), ET(*,G,I), ET(S,G,I), 5767 ET(S,G,rpt,I)) 5769 (+----------------+-----------------+------------------------------------+ 5770 | Value Name | Value | Explanation | 5771 | 5772 +----------------+-----------------+------------------------------------+ 5773 | J/P_HoldTime | from message | Holdtime from Join/Prune Message | 5774 | 5775 +----------------+-----------------+------------------------------------+ 5777 See details of JT(*,G) for the Holdtime that is included in Join/Prune 5778 Messages. 5780 Timer Names: Prune-Pending Timer (PPT(*,*,RP,I), PPT(*,G,I), PPT(S,G,I), 5781 PPT(S,G,rpt,I)) 5783 T+---------------------------+---------------------+---------------------+ 5784 |Value Name | Value | Explanation | 5785 | 5786 +---------------------------+---------------------+---------------------+ 5787 |J/P_Override_Interval(I) | Default: | Short period after | 5788 | | Effective_ | a join or prune to | 5789 | | Propagation_ | allow other | 5790 | | Delay(I) + | routers on the LAN | 5791 | | EffectiveOverride_ | to override the | 5792 | | Interval(I) | join or prune | 5793 | 5794 +---------------------------+---------------------+---------------------+ 5796 Note that both the Effective_Propagation_Delay(I) and the 5797 Effective_Override_Interval(I) are interface specific values that may 5798 change when Hello messages are received (see section 4.3.3). 5800 Timer Names: Assert Timer (AT(*,G,I), AT(S,G,I)) 5802 m+---------------------------+----------------------+--------------------+ 5803 | Value Name | Value | Explanation | 5804 | 5805 +---------------------------+----------------------+--------------------+ 5806 | Assert_Override_Interval | Default: 3 secs | Short interval | 5807 | | | before an assert | 5808 | | | times out where | 5809 | | | the assert winner | 5810 | | | resends an Assert | 5811 | | | message | 5812 | 5813 +---------------------------+----------------------+--------------------+ 5814 | Assert_Time | Default: 180 secs | Period after last | 5815 | | | assert before | 5816 | | | assert state is | 5817 | | | timed out | 5818 | 5819 +---------------------------+----------------------+--------------------+ 5821 Note that for historical reasons, the Assert message lacks a Holdtime 5822 field. Thus changing the Assert Time from the default value is not 5823 recommended. 5825 Timer Names: Upstream Join Timer (JT(*,*,RP), JT(*,G), JT(S,G)) 5827 m+-------------+--------------------+-------------------------------------+ 5828 |Value Name | Value | Explanation | 5829 | 5830 +-------------+--------------------+-------------------------------------+ 5831 |t_periodic | Default: 60 secs | Period between Join/Prune Messages | 5832 | 5833 +-------------+--------------------+-------------------------------------+ 5834 |t_suppressed | rand(1.1 * | Suppression period when someone | 5835 | | t_periodic, 1.4 * | else sends a J/P message so we | 5836 | | t_periodic) when | don't need to do so. | 5837 | | Suppression_ | | 5838 | | Enabled(I) is | | 5839 | | true, 0 otherwise | | 5840 | 5841 +-------------+--------------------+-------------------------------------+ 5842 |t_override | rand(0, Effective_ | Randomized delay to prevent | 5843 | | Override_ | response implosion when sending a | 5844 | | Interval(I)) | join message to override someone | 5845 | | | else's Prune message. | 5846 | 5847 +-------------+--------------------+-------------------------------------+ 5849 t_periodic may be set to take into account such things as the configured 5850 bandwidth and expected average number of multicast route entries for the 5851 attached network or link (e.g., the period would be longer for lower- 5852 speed links, or for routers in the center of the network that expect to 5853 have a larger number of entries). If the Join/Prune-Period is modified 5854 during operation, these changes should be made relatively infrequently 5855 and the router should continue to refresh at its previous Join/Prune- 5856 Period for at least Join/Prune-Holdtime, in order to allow the upstream 5857 router to adapt. 5859 The holdtime specified in a Join/Prune message should be set to (3.5 * 5860 t_periodic). 5862 t_override depends on the Effective_Override_Interval of the upstream | 5863 interface which may change when Hello messages are received. 5865 t_suppressed depends on the Suppression State of the upstream interface 5866 (Section 4.3.3) and becomes zero when suppression is disabled. 5868 Timer Name: Upstream Override Timer (OT(S,G,rpt)) 5870 m+---------------+---------------------------+---------------------------+ 5871 | Value Name | Value | Explanation | 5872 | 5873 +---------------+---------------------------+---------------------------+ 5874 | t_override | see Upstream Join Timer | see Upstream Join Timer | 5875 | 5876 +---------------+---------------------------+---------------------------+ 5878 The upstream Override Timer is only ever set to t_override; this value 5879 is defined in the section on Upstream Join Timers. 5881 Timer Name: Keepalive Timer (KAT(S,G)) 5883 m+-----------------------+------------------------+----------------------+ 5884 | Value Name | Value | Explanation | 5885 | 5886 +-----------------------+------------------------+----------------------+ 5887 | Keepalive_Period | Default: 210 secs | Period after last | 5888 | | | (S,G) data packet | 5889 | | | during which (S,G) | 5890 | | | Join state will be | 5891 | | | maintained even in | 5892 | | | the absence of | 5893 | | | (S,G) Join | 5894 | | | messages. | 5895 | 5896 +-----------------------+------------------------+----------------------+ 5897 | RP_Keepalive_Period | ( 3 * Register_ | As | 5898 | | Suppression_Time ) | Keepalive_Period, | 5899 | | + Register_ | but at the RP when | 5900 | | Probe_Time | a Register-Stop is | 5901 | | | sent. | 5902 | 5903 +-----------------------+------------------------+----------------------+ 5904 The normal keepalive period for the KAT(S,G) defaults to 210 seconds. 5905 However at the RP, the keepalive period must be at least the 5906 Register_Suppression_Time or the RP may time out the (S,G) state before 5907 the next Null-Register arrives. Thus the KAT(S,G) is set to 5908 max(Keepalive_Period, RP_Keepalive_Period) when a Register-Stop is sent. 5910 Timer Name: Register-Stop Timer (RST(S,G)) 5912 m+----------------------------+--------------------+---------------------+ 5913 |Value Name | Value | Explanation | 5914 | 5915 +----------------------------+--------------------+---------------------+ 5916 |Register_Suppression_Time | Default: 60 secs | Period during | 5917 | | | which a DR stops | 5918 | | | sending Register- | 5919 | | | encapsulated data | 5920 | | | to the RP after | 5921 | | | receiving a | 5922 | | | Register-Stop | 5923 | | | message. | 5924 | 5925 +----------------------------+--------------------+---------------------+ 5926 |Register_Probe_Time | Default: 5 secs | Time before RST | 5927 | | | expires when a DR | 5928 | | | may send a Null- | 5929 | | | Register to the RP | 5930 | | | to cause it to | 5931 | | | resend a Register- | 5932 | | | Stop message. | 5933 | 5934 +----------------------------+--------------------+---------------------+ 5935 If the the Register_Suppression_Time or the Register_Probe_Time are | 5936 configured to values other than the defaults it MUST be ensured that the | 5937 value of the Register_Probe_Time is less than half the value of the | 5938 Register_Suppression_Time to prevent a possible negative value in the | 5939 setting of the Register-Stop Timer. 5941 5. IANA Considerations 5943 5.1. PIM Address Family 5945 The PIM Address Family field was chosen to be 8 bits as a tradeoff 5946 between packet format and use of the IANA assigned numbers. Since when 5947 the PIM packet format was designed only 15 values were assigned for 5948 Address Families, and large numbers of new Address Family values were 5949 not envisioned, 8 bits seemed large enough. However, the IANA assigns 5950 Address Families in a 16-bit field. Therefore, the PIM Address Family 5951 is allocated as follows: 5953 Values 0 through 127 are designated to have the same meaning as 5954 IANA-assigned Address Family Numbers [6]. 5956 Values 128 through 250 are designated to be assigned for PIM by the | 5957 IANA based upon IESG Approval, as defined in [8]. 5959 Values 251 through 255 are designated for Private Use, as defined 5960 in [8]. 5962 5.2. PIM Hello Options 5964 Values 17 through 65000 are to be assigned by the IANA. Since the space 5965 is large, they may be assigned as First Come First Served as defined in 5966 [8]. Such assignments are valid for one year, and may be renewed. 5967 Permanent assignments require a specification (see "Specification 5968 Required" in [8].) 5970 6. Security Considerations 5972 The IPsec authentication header [7] MAY be used to provide data 5973 integrity protection and groupwise data origin authentication of PIM 5974 protocol messages. Authentication of PIM messages can protect against 5975 unwanted behaviors caused by unauthorized or altered PIM messages. 5977 6.1. Attacks based on forged messages 5979 The extent of possible damage depends on the type of counterfeit 5980 messages accepted. We next consider the impact of possible forgeries, 5981 including forged link-local (Join/Prune, Hello, and Assert) and forged 5982 unicast (Register and Register-Stop) messages. 5984 6.1.1. Forged link-local messages 5986 Join/Prune, Hello, and Assert messages are all sent to the link-local 5987 ALL_PIM_ROUTERS multicast addresses, and thus are not forwarded by a 5988 compliant router. A forged message of this type can only reach a LAN if 5989 it was sent by a local host or if it was allowed onto the LAN by a 5990 compromised or non-compliant router. 5992 1. A forged Join/Prune message can cause multicast traffic to be 5993 delivered to links where there are no legitimate requesters, 5994 potentially wasting bandwidth on that link. A forged leave message 5995 on a multi-access LAN is generally not a significant attack in PIM, 5996 because any legitimately joined router on the LAN would override 5997 the leave with a join before the upstream router stops forwarding 5998 data to the LAN. 6000 2. By forging a Hello message, an unauthorized router can cause 6001 itself to be elected as the designated router on a LAN. The 6002 designated router on a LAN is (in the absence of asserts) 6003 responsible for forwarding traffic to that LAN on behalf of any 6004 local members. The designated router is also responsible for 6005 register-encapsulating to the RP any packets that are originated by 6006 hosts on the LAN. Thus, the ability of local hosts to send and 6007 receive multicast traffic may be compromised by a forged Hello 6008 message. 6010 3. By forging an Assert message on a multi-access LAN, an attacker 6011 could cause the legitimate designated forwarder to stop forwarding 6012 traffic to the LAN. Such a forgery would prevent any hosts 6013 downstream of that LAN from receiving traffic. 6015 6.1.2. Forged unicast messages 6017 Register messages and Register-Stop messages are forwarded by 6018 intermediate routers to their destination using normal IP forwarding. 6019 Without data origin authentication, an attacker who is located anywhere 6020 in the network may be able to forge a Register or Register-Stop message. 6021 We consider the effect of a forgery of each of these messages next. 6023 1 By forging a Register message, an attacker can cause the RP to 6024 inject forged traffic onto the shared multicast tree. 6026 2 By forging a Register-stop message, an attacker can prevent a 6027 legitimate DR from Registering packets to the RP. This can prevent 6028 local hosts on that LAN from sending multicast packets. 6030 The above two PIM messages are not changed by intermediate routers and 6031 need only be examined by the intended receiver. Thus these messages can 6032 be authenticated end-to-end, using AH. Attacks on Register and 6033 Register-Stop messages do not apply to a PIM-SSM-only implementation, as 6034 these messages are not required for PIM-SSM. 6036 6.2. Non-cryptographic Authentication Mechanisms 6038 A PIM router SHOULD provide an option to limit the set of neighbors from 6039 which it will accept Join/Prune, Assert, and Hello messages. Either 6040 static configuration of IP addresses or an IPsec security association 6041 may be used. Furthermore, a PIM router SHOULD NOT accept protocol 6042 messages from a router from which it has not yet received a valid Hello 6043 message. 6045 A Designated Router MUST NOT register-encapsulate a packet and send it 6046 to the RP unless the source address of the packet is a legal address for 6047 the subnet on which the packet was received. Similarly, a Designated 6048 Router SHOULD NOT accept a Register-Stop packet whose IP source address 6049 is not a valid RP address for the local domain. 6051 An implementation SHOULD provide a mechanism to allow an RP to restrict 6052 the range of source addresses from which it accepts Register- 6053 encapsulated packets. 6055 All options that restrict the range of addresses from which packets are 6056 accepted MUST default to allowing all packets. 6058 6.3. Authentication using IPsec 6060 The IPsec [7] transport mode using the Authentication Header (AH) is the 6061 recommended method to prevent the above attacks against PIM. The 6062 specific AH authentication algorithm and parameters, including the 6063 choice of authentication algorithm and the choice of key, are configured 6064 by the network administrator. When IPsec authentication is used, a PIM 6065 router should reject (drop without processing) any unauthorized PIM 6066 protocol messages. 6068 As of this writing, the IPsec anti-replay option does not handle the 6069 case of a Security Association identified by a multicast destination 6070 address. Thus, the anti-replay option currently must be disabled on 6071 these Security Associations. Until replay prevention for link-local 6072 multicast messages is addressed (one such proposal is [14]), the anti- 6073 replay option SHOULD be enabled on all security associations having a 6074 unicast destination address. 6076 To use IPsec, the administrator of a PIM network configures each PIM 6077 router with one or more Security Associations and associated SPI(s) that 6078 are used by senders to sign PIM protocol messages and are used by 6079 receivers to authenticate received PIM protocol messages. This document 6080 does not describe protocols for establishing Security Associations. It 6081 assumes that manual configuration of Security Associations is performed, 6082 but it does not preclude the use of a negotiation protocol such as The 6083 Internet Key Exchange [13] to establish Security Associations. 6085 The following sections describe the Security Associations required to 6086 protect PIM protocol messages. 6088 6.3.1. Protecting link-local multicast messages 6090 The network administrator defines a Security Association (SA) and 6091 Security Parameters Index (SPI) that is to be used to authenticate all 6092 link-local PIM protocol messages (Hello, Join/Prune, and Assert) on each 6093 link in a PIM domain. All link-local PIM protocol messages use SPI 0. 6095 The Security Policy Database at a PIM router should be configured to 6096 ensure that all incoming and outgoing Join/Prune, Assert, and Hello 6097 packets use the SA associated with the interface to which the packet is 6098 sent. 6100 Note that, according to [7] there is nominally a different Security 6101 Association Database (SAD) for each router interface. Thus, the 6102 selected Security Association for an inbound PIM packet can vary 6103 depending on the interface on which the packet arrived. This fact 6104 allows the network administrator to use different authentication methods 6105 for each link, even though the destination address is the same for all 6106 link-local PIM packets, regardless of interface. 6108 6.3.2. Protecting unicast messages 6110 IPSec can also be used to provide data origin authentication and data 6111 integrity protection for the Register and Register-Stop unicast 6112 messages. 6114 6.3.2.1. Register messages 6116 The Security Policy Database at every PIM router is configured to select 6117 a Security Association to use when sending PIM Register packets to each 6118 rendezvous point. 6120 In the most general mode of operation, the Security Policy Database at 6121 each DR is configured to select a unique SA and SPI for traffic sent to 6122 each RP. This allows each DR to have a different authentication 6123 algorithm and key to talk to the RP. However, this creates a daunting 6124 key management and distribution problem for the network administrator. 6125 Therefore, it may be preferable in PIM domains where all Designated 6126 Routers are under a single administrative control, to use the same 6127 authentication algorithm parameters (including the key) for all 6128 Registered packets in a domain, regardless of who is the RP and 6129 regardless of who is the DR. 6131 In this "single shared key" mode of operation, the network administrator 6132 must choose an SPI for each DR that will be used to send it PIM protocol 6133 packets. The Security Policy Database at every DR is configured to 6134 select a Security Association (including the authentication algorithm, 6135 authentication parameters, and this SPI) when sending Register messages 6136 to this RP. 6138 By using a single authentication algorithm and associated parameters, 6139 the key distribution problem is simplified. Note however, that this 6140 method has the property that, in order to change the authentication 6141 method or authentication key used, all routers in the domain must be 6142 updated. 6144 6.3.2.2. Register-Stop messages 6146 Similarly, the Security Policy Database at each Rendezvous Point should 6147 be configured to choose a Security Association to use when sending 6148 Register-Stop messages. Because Register-Stop messages are unicast to 6149 the destination DR, a different Security Association and a potentially 6150 unique SPI is required for each DR. 6152 In order to simplify the management problem, it may be acceptable to use 6153 the same authentication algorithm and authentication parameters, 6154 regardless of the sending RP and regardless of the destination DR. 6155 Although a unique Security Association is needed for each DR, the same 6156 authentication algorithm and authentication algorithm parameters (secret 6157 key) can be shared by all DRs and by all RPs. 6159 6.4. Denial of Service Attacks 6161 There are a number of possible denial of service attacks against PIM 6162 that can be caused by generating false PIM protocol messages or even by 6163 generating data false traffic. Authenticating PIM protocol traffic 6164 prevents some, but not all of these attacks. Two of the possible 6165 attacks include: 6167 - Sending packets to many different group addresses quickly can be a 6168 denial of service attack in and of itself. This will cause many 6169 register-encapsulated packets, loading the DR, the RP, and the 6170 routers between the DR and the RP. 6172 - Forging Join messages can cause a multicast tree to get set up. A 6173 large number of forged joins can consume router resources and 6174 result in denial of service. 6176 7. Authors' Addresses 6178 Bill Fenner 6179 AT&T Labs - Research 6180 75 Willow Road 6181 Menlo Park, CA 94025 6182 fenner@research.att.com 6184 Mark Handley 6185 Department of Computer Science 6186 University College London 6187 Gower Street 6188 London WC1E 6BT 6189 United Kingdom 6190 M.Handley@cs.ucl.ac.uk 6191 Hugh Holbrook 6192 Cisco Systems 6193 170 W. Tasman Drive 6194 San Jose, CA 95134 6195 holbrook@cisco.com 6197 Isidor Kouvelas 6198 Cisco Systems 6199 170 W. Tasman Drive 6200 San Jose, CA 95134 6201 kouvelas@cisco.com 6203 8. Acknowledgments 6205 PIM-SM was designed over many years by a large group of people, 6206 including ideas, comments, and corrections from Deborah Estrin, Dino 6207 Farinacci, Ahmed Helmy, David Thaler, Steve Deering, Van Jacobson, C. 6208 Liu, Puneet Sharma, Liming Wei, Tom Pusateri, Tony Ballardie, Scott 6209 Brim, Jon Crowcroft, Paul Francis, Joel Halpern, Horst Hodel, Polly 6210 Huang, Stephen Ostrowski, Lixia Zhang, Girish Chandranmenon, Brian 6211 Haberman, Hal Sandick, Mike Mroz, Garry Kump, Pavlin Radoslavov, Mike | 6212 Davison, James Huang, Christopher Thomas Brown, and James Lingard. 6214 Thanks are due to the American Licorice Company, for its obscure but 6215 possibly essential role in the creation of this document. 6217 9. Normative References 6219 [1] B. Cain, S. Deering, I. Kouvelas, B. Fenner, A. Thyagarajan, 6220 "Internet Group Management Protocol, Version 3", RFC 3376. 6222 [2] S.E. Deering, "Host extensions for IP multicasting", RFC 1112, Aug 6223 1989. 6225 [3] S. Deering, W. Fenner, B. Haberman, "Multicast Listener Discovery 6226 (MLD) for IPv6", RFC 2710. 6228 [4] S. Deering, R. Hinden, "Internet Protocol, Version 6 (IPv6) 6229 Specification", RFC 2460. 6231 [5] H. Holbrook, B. Cain, "Source-Specific Multicast for IP", draft- 6232 ietf-ssm-arch-04.txt, work in progress. 6234 [6] IANA, "Address Family Numbers", linked from 6235 http://www.iana.org/numbers.html 6237 [7] S. Kent, R. Atkinson, "Security Architecture for the Internet 6238 Protocol.", RFC 2401. 6240 [8] T. Narten , H. Alvestrand, "Guidelines for Writing an IANA 6241 Considerations Section in RFCs", RFC 2434. 6243 10. Informative References 6245 [9] T. Bates , R. Chandra , D. Katz , Y. Rekhter, "Multiprotocol 6246 Extensions for BGP-4", RFC 2283 6248 [10] D. Black, "Differentiated Services and Tunnels", RFC 2983. 6250 [11] W. Fenner, M. Handley, R. Kermode, D. Thaler, "Bootstrap Router 6251 (BSR) Mechanism for PIM Sparse Mode", draft-ietf-pim-sm-bsr-03.txt, 6252 work in progress. 6254 [12] M. Handley, I. Kouvelas, T. Speakman, L. Vicisano, "Bi-directional 6255 Protocol Independent Multicast", draft-ietf-pim-bidir-05.txt, work 6256 in progress. 6258 [13] D. Harkins, D. Carrell, "The Internet Key Exchange (IKE)", RFC 6259 2409. 6261 [14] S. Kent, "IP Encapsulating Security Payload (ESP)", draft-ietf- 6262 ipsec-esp-v3-06.txt, work in progress. 6264 [15] P. Savola, B. Haberman, "Embedding the Rendezvous Point (RP) 6265 Address in an IPv6 Multicast Address" draft-ietf-mboned- 6266 embeddedrp-04.txt, work in progress. 6268 [16] D. Thaler, "Interoperability Rules for Multicast Routing 6269 Protocols", RFC 2715. 6271 11. Appendix A: PIM Multicast Border Router Behavior | 6273 In some cases PIM-SM domains will interconnect with non-PIM multicast | 6274 domains. In these cases, the border routers of the PIM domain speak | 6275 PIM-SM on some interfaces and speak other multicast routing protocols on | 6276 other interfaces. Such routers are termed PIM Multicast Border Routers | 6277 or PMBRs. In general, RFC 2715 [16] provides rules for interoperability | 6278 between different multicast routing protocols. In this section we | 6279 specify how PMBRs differ from regular PIM-SM routers. | 6281 From the point of view of PIM-SM, a PMBR has two tasks: | 6283 o To ensure that traffic from sources outside the PIM-SM domain reaches | 6284 receivers inside the domain. | 6286 o To ensure that traffic from sources inside the PIM-SM domain reaches | 6287 receivers outside the domain. | 6289 We note that multiple PIM-SM domains are sometimes connected together | 6290 using protocols such as MSDP, which provides information about active | 6291 external sources, but does not follow RFC 2715. In such cases the | 6292 domains are not connected via PMBRs because Join(S,G) messages traverse | 6293 the border between domains. A PMBR is required when no PIM messages can | 6294 traverse the border. | 6296 11.1. Sources External to the PIM-SM Domain | 6298 A PMBR needs to ensure that traffic from multicast sources external to | 6299 the PIM-SM domain reaches receivers inside the domain. The PMBR will | 6300 follow the rules in RFC 2715, such that traffic from external sources | 6301 reaches the PMBR itself. | 6303 According to RFC 2715, the PIM-SM component of the PMBR will receive an | 6304 (S,G) Creation event when data from an (S,G) data packet from an | 6305 external source first reaches the PMBR. If RPF_interface(S) is an | 6306 interface in the PIM-SM domain, the packet cannot be originated into the | 6307 PIM domain at this router, and the PIM-SM component of the PMBR will not | 6308 process the packet. Otherwise the PMBR will then act exactly as if it | 6309 were the DR for this source (see Section 4.4.1), with the following | 6310 modifications: | 6312 o The Border-bit is set in all PIM Register message sent for these | 6313 sources. | 6315 o DirectlyConnected(S) is treated as being TRUE for these sources. | 6317 o The PIM-SM forwarding rule "iif == RPF_interface(S)" is relaxed to be | 6318 TRUE if iif is any interface that is not part of the PIM-SM component | 6319 of the PMBR (see Section 4.2). | 6321 11.2. Sources Internal to the PIM-SM Domain | 6323 A PMBR needs to ensure that traffic from sources inside the PIM-SM | 6324 domain reaches receivers outside the domain. Using terminology from RFC | 6325 2715, there are two possible scenarios for this: | 6327 o Another component of the PMBR is a wildcard receiver. In this case | 6328 the PIM-SM component of the PMBR must ensure that traffic from all | 6329 internal sources reaches the PMBR until it is informed otherwise. | 6331 Note that certain profiles of PIM-SM, e.g., PIM-SSM, PIM-SM with | 6332 Embedded RP, cannot interoperate with a neighboring wildcard receiver | 6333 domain. | 6335 o No other component of the PMBR is a wildcard receiver. In this case | 6336 the PMBR will receive explicit information as to which groups or | 6337 (source,group) pairs the external domains wish to receive. | 6339 In the former case, the PMBR will need to send a Join(*,*,RP) to all the | 6340 active RPs in the PIM-SM domain. It may also send a Join(*,*,RP) to all | 6341 the candidate RPs in the PIM-SM domain. This will cause all traffic in | 6342 the domain to reach the PMBR. The PMBR may then act as if it were a DR | 6343 with directly connected receivers, and trigger the transition to a | 6344 shortest path tree (see Section 4.2.1). | 6346 In the latter case, the PMBR will not need to send Join(*,*,RP) | 6347 messages. However the PMBR will still need to act as a DR with directly | 6348 connected receivers on behalf of the external receivers in terms of | 6349 being able to switch to the shortest-path tree for internally-reached | 6350 sources. | 6352 According to RFC 2715, the PIM-SM component of the PMBR may receive a | 6353 number of alerts generated by events in the external routing components. | 6354 To implement the above behavior, one reasonable way to map these alerts | 6355 into PIM-SM state as follows: | 6357 o When a PIM-SM component receives an (S,G) Prune alert, it sets | 6358 local_receiver_include(S,G,I) to FALSE for the discard interface. | 6360 o When a PIM-SM component receives a (*,G) Prune alert, it sets | 6361 local_receiver_include(*,G,I) to FALSE for the discard interface. | 6363 o When a PIM-SM component receives an (S,G) Join alert, it sets | 6364 local_receiver_include(S,G,I) to TRUE for the discard interface. | 6366 o When a PIM-SM component receives a (*,G) Join alert, it sets | 6367 local_receiver_include(*,G,I) to TRUE for the discard interface. | 6369 o When a PIM-SM component receives a (*,*) Join alert, it sets | 6370 DownstreamJPState(*,*,RP,I) to Join state on the discard interface for | 6371 all RPs in the PIM-SM domain. | 6373 o When a PIM-SM component receives a (*,*) Prune alert, then it sets | 6374 DownstreamJPState(*,*,RP,I) to NoInfo state on the discard interface | 6375 for all RPs in the PIM-SM domain. | 6377 We refer above to the discard interface because the macros and state | 6378 machines are interface-specific, but we need to have PIM state that is | 6379 not associated with any actual PIM-SM interface. Implementors are free | 6380 to implement this in any reasonable manner. | 6382 Note that these state changes will then cause additional PIM-SM state | 6383 machine transitions in the normal way. | 6385 These rules are however not sufficient to allow pruning off the (*,*,RP) | 6386 tree. Some additional rules provide guidance as to one way this may be | 6387 done: | 6389 o If the PMBR has joined on the (*,*,RP) tree, then it should set | 6390 DownstreamJPState(*,G,I) to JOIN on the discard interface for all | 6391 active groups. | 6393 o If the router receives a (S,G) prune alert it will need to set | 6394 DownstreamJPState(S,G,rpt,I) to PRUNE on the discard interface. | 6396 o If the router receives a (*,G) prune alert, it will need to set | 6397 DownstreamJPState(S,G,rpt,I) to PRUNE on the discard interface for all | 6398 active sources sending to G. | 6400 The rationale for this is that there is no way in PIM-SM to prune | 6401 traffic off the (*,*,RP) tree, except by Joining the (*,G) tree and then | 6402 pruning each source individually. | 6403 12. Index 6404 Assert(*,G). . . . . . . . . . . . . . . . . . . . . . . . . . . .27,127 6405 Assert(S,G). . . . . . . . . . . . . . . . . . . . . . . . . . . .27,127 6406 AssertCancel(*,G). . . . . . . . . . . . . . . . . . . . . . . . . 97,99 6407 AssertCancel(S,G). . . . . . . . . . . . . . . . . . . . . . . .79,90,99 6408 AssertTimer(*,G,I) . . . . . . . . . . . . . . . . . . . . .16,25,91,131 6409 AssertTimer(S,G,I) . . . . . . . . . . . . . . . . . . . . .18,25,83,131 6410 AssertTrackingDesired(*,G,I) . . . . . . . . . . . . . . . . . .93,94,96 6411 AssertTrackingDesired(S,G,I) . . . . . . . . . . . . . . . . 85,85,87,89 6412 AssertWinerMetric(*,G,I) . . . . . . . . . . . . . . . . . . . . . . 17 6413 AssertWinner(*,G,I). . . . . . . . . . . . . . . . . .17,22,25,93,97,100 6414 AssertWinner(S,G,I). . . . . . . . . . . . . . . . 18,23,25,85,89,99,100 6415 AssertWinnerMetric(*,G,I). . . . . . . . . . . . . . . . . . . . .97,100 6416 AssertWinnerMetric(S,G,I). . . . . . . . . . . . . . . . . . . 18,89,100 6417 assert_metric. . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 6418 Assert_Override_Interval . . . . . . . . . . . . . . . . . . . 89,96,131 6419 Assert_Time. . . . . . . . . . . . . . . . . . . . . . . . . . 89,96,131 6420 AT(*,G,I). . . . . . . . . . . . . . . . . . . . . . . .16,25,91,128,131 6421 AT(S,G,I). . . . . . . . . . . . . . . . . . . . . . . .18,25,83,128,131 6422 CheckSwitchToSpt(S,G). . . . . . . . . . . . . . . . . . . . . . . 27,28 6423 CouldAssert(*,G,I) . . . . . . . . . . . . . . . . . . . .91,93,94,95,98 6424 CouldAssert(S,G,I) . . . . . . . . . . . . . . . . . . 83,85,87,88,89,98 6425 CouldRegister(S,G) . . . . . . . . . . . . . . . . . . . . . . . . 38,40 6426 Default_Hello_Holdtime . . . . . . . . . . . . . . . . . . . . . . . 33 6427 DirectlyConnected(S) . . . . . . . . . . . . . . . . . . 27,27,29,40,142 6428 DownstreamJPState(*,*,RP,I). . . . . . . . . . . . . . . . . . . .23,144 6429 DownstreamJPState(*,G,I) . . . . . . . . . . . . . . . . . . . . . . 23 6430 DownstreamJPState(S,G,I) . . . . . . . . . . . . . . . . . . . . . 24,40 6431 DownstreamJPState(S,G,rpt,I) . . . . . . . . . . . . . . . . . . . . 24 6432 DR(I). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 6433 dr_is_better(a,b,I). . . . . . . . . . . . . . . . . . . . . . . . 33,33 6434 DR_Priority. . . . . . . . . . . . . . . . . . . . . . . . . . .31,32,33 6435 Effective_Override_Interval(I) . . . . . . . . . . . . . . . .36,113,131 6436 Effective_Propagation_Delay(I) . . . . . . . . . . . . . . . . . .35,131 6437 ET(*,*,RP,I) . . . . . . . . . . . . . . . . . . . . . . . 15,46,127,130 6438 ET(*,G,I). . . . . . . . . . . . . . . . . . . . . . . . . 16,49,128,130 6439 ET(S,G,I). . . . . . . . . . . . . . . . . . . . . . . . . 18,53,128,130 6440 ET(S,G,rpt,I). . . . . . . . . . . . . . . . . . . . . .21,56,58,128,130 6441 GenID. . . . . . . . . . . . . . . . . . . 16,18,20,31,63,67,70,72,83,91 6442 Hash_Function. . . . . . . . . . . . . . . . . . . . . . . . . . .13,105 6443 Hello_Holdtime . . . . . . . . . . . . . . . . . . . . . . . . . .33,130 6444 Hello_Period . . . . . . . . . . . . . . . . . . . . . . . . . . .31,129 6445 HT(I). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .31,129 6446 IGMP . . . . . . . . . . . . . . . . . . . . . . . . . 7,9,17,23,101,104 6447 immediate_olist(*,*,RP). . . . . . . . . . . . . . . . . . . . . . 22,63 6448 immediate_olist(*,G) . . . . . . . . . . . . . . . . . . . . . . . 22,68 6449 immediate_olist(S,G) . . . . . . . . . . . . . . . . . . . . . .22,40,72 6450 infinite_assert_metric() . . . . . . . . . . . . . . . . . . . . . . 98 6451 inherited_olist(S,G) . . . . . . . . . . . . . . . . .22,27,43,72,85,107 6452 inherited_olist(S,G,rpt) . . . . . . . . . . . . . . . 22,27,29,76,78,80 6453 Interface_Address_List . . . . . . . . . . . . . . . . . . . . . . . 31 6454 I_Am_Assert_Loser(*,G,I) . . . . . . . . . . . . . . . . . . . . . . 25 6455 I_Am_Assert_Loser(S,G,I) . . . . . . . . . . . . . . . . . . . . . . 25 6456 I_am_DR(I) . . . . . . . . . . . . . . . . . . . . . . . .22,33,40,85,93 6457 I_am_RP(G) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43,44 6458 J/P_Holdtime . . . . . . . . . . . . . .47,50,54,58,64,69,74,120,130,132 6459 J/P_Override_Interval(I) . . . . . . . . . . . . . . 47,51,54,58,120,131 6460 JoinDesired(*,*,RP). . . . . . . . . . . . . . . . . . . . . . . . 63,77 6461 JoinDesired(*,G) . . . . . . . . . . . . . . . . . . . . .17,68,77,85,97 6462 JoinDesired(S,G) . . . . . . . . . . . . . . . . . . . 19,29,72,85,88,90 6463 joins(*,*,RP(G)) . . . . . . . . . . . . . . . . . . . . . . . . . . 22 6464 joins(*,*,RP). . . . . . . . . . . . . . . . . . . . . . . . 22,23,85,93 6465 joins(*,G) . . . . . . . . . . . . . . . . . . . . . . . . . 22,23,85,93 6466 joins(S,G) . . . . . . . . . . . . . . . . . . . . . . . . . . .22,23,85 6467 JT(*,*,RP) . . . . . . . . . . . . . . . . . . . . . . . . 15,61,128,132 6468 JT(*,G). . . . . . . . . . . . . . . . . . . . . . . . . . 17,66,128,132 6469 JT(S,G). . . . . . . . . . . . . . . . . . . . . . . . . . 18,71,128,132 6470 KAT(S,G) . . . . . . . . . . . . . . . .19,26,27,28,40,43,72,107,128,133 6471 KeepaliveTimer(S,G). . . . . . . . . 19,26,27,27,28,40,43,72,107,128,133 6472 Keepalive_Period . . . . . . . . . . . . . . . . . . . . . . . . .27,133 6473 lan_delay_enabled(I) . . . . . . . . . . . . . . . . . . . . . . . 34,36 6474 LAN_Prune_Delay. . . . . . . . . . . . . . . . . . . . . . . . . . . 31 6475 local_receiver_exclude(S,G,I). . . . . . . . . . . . . . . . . . . . 23 6476 local_receiver_include(*,G,I). . . . . . . . . . . . . . . . . 23,93,143 6477 local_receiver_include(S,G,I). . . . . . . . . . . . . . . . . . . 23,85 6478 local_receiver_include(S,G,I). . . . . . . . . . . . . . . . . . . . 143 6479 lost_assert(*,G) . . . . . . . . . . . . . . . . . . . . . . . .22,24,85 6480 lost_assert(*,G,I) . . . . . . . . . . . . . . . . . . . . . . 22,24,100 6481 lost_assert(S,G) . . . . . . . . . . . . . . . . . . . . . . . . . 22,24 6482 lost_assert(S,G,I) . . . . . . . . . . . . . . . . . . . . . . .23,24,99 6483 lost_assert(S,G,rpt) . . . . . . . . . . . . . . . . . . . . . . . . 24 6484 lost_assert(S,G,rpt,I) . . . . . . . . . . . . . . . . . . . . . . 24,99 6485 MBGP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7,8 6486 MFIB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7,14 6487 MLD. . . . . . . . . . . . . . . . . . . . . . . . . . 7,9,17,23,101,104 6488 MRIB . . . . . . . . . . . . . . .7,8,12,16,20,25,61,65,65,75,98,102,127 6489 MRIB.next_hop(host). . . . . . . . . . . . . . . . . . . . . 25,25,61,63 6490 my_assert_metric(S,G,I). . . . . . . . . . . . . . . . . .85,89,91,93,98 6491 NBR(Interface,IP_address). . . . . . . . . . . . . . . . .26,36,61,63,65 6492 NLT(N,I) . . . . . . . . . . . . . . . . . . . . . . . . . 15,33,127,130 6493 OT(S,G,rpt). . . . . . . . . . . . . . . . . . . . . . . . 21,76,128,133 6494 Override_Interval(I) . . . . . . . . . . . . . . 14,31,34,36,113,129,131 6495 packet_arrives_on_rp_tunnel(pkt) . . . . . . . . . . . . . . . . . . 43 6496 pim_exclude(S,G) . . . . . . . . . . . . . . . . . . . . . . 22,23,28,85 6497 pim_include(*,G) . . . . . . . . . . . . . . . . . . . 17,22,22,28,85,93 6498 pim_include(S,G) . . . . . . . . . . . . . . . . . . . . .19,22,23,28,85 6499 PPT(*,*,RP,I). . . . . . . . . . . . . . . . . . . . . . . 15,46,127,131 6500 PPT(*,G,I) . . . . . . . . . . . . . . . . . . . . . . . . 16,49,128,131 6501 PPT(S,G,I) . . . . . . . . . . . . . . . . . . . . . . . . 18,53,128,131 6502 PPT(S,G,rpt,I) . . . . . . . . . . . . . . . . . . . . .21,56,58,128,131 6503 Propagation_Delay(I) . . . . . . . . . . . . . . . . . . . 31,35,129,131 6504 Propagation_delay_default. . . . . . . . . . . . . . . . . . . . .35,129 6505 PruneDesired(S,G,rpt). . . . . . . . . . . . . . . . . . . . 78,79,88,90 6506 prunes(S,G,rpt). . . . . . . . . . . . . . . . . . . . . . . . .22,24,85 6507 Register-Stop(*,G) . . . . . . . . . . . . . . . . . . . . . . . . . 41 6508 Register-Stop(S,G) . . . . . . . . . . . . . . . . . . . . . . . . . 43 6509 Register-StopTimer(S,G). . . . . . . . . . . . . . . . . . 38,39,128,133 6510 Register_Probe_Time. . . . . . . . . . . . . . . . . . . . . . 39,44,133 6511 Register_Suppression_Time. . . . . . . . . . . . . . . . . . . 39,44,133 6512 RP(G). . . . . . . . . . . . . . 6,22,25,40,43,49,68,76,85,93,98,101,127 6513 RPF. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 6514 RPF'(*,G). . . . . . . . . . . . . . . . . . 25,29,66,67,70,76,77,97,100 6515 RPF'(S,G). . . . . . . . . . . . . . . . . . . . . 25,29,71,76,77,90,100 6516 RPF'(S,G,rpt). . . . . . . . . . . . . . . . . . . . . . . .25,76,78,101 6517 RPF_interface. . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 6518 RPF_interface(host). . . . . . . . 25,27,29,40,68,69,74,85,93,99,107,142 6519 RPTJoinDesired(G). . . . . . . . . . . . . . . . . . . . . . . .77,80,93 6520 rpt_assert_metric(G,I) . . . . . . . . . . . . . . . . . . . . . . 96,98 6521 RST(S,G) . . . . . . . . . . . . . . . . . . . . . . . . . 38,39,128,133 6522 SPTbit(S,G). . . . . . . . . .20,27,29,43,52,73,76,78,85,85,89,90,99,107 6523 spt_assert_metric(S,I) . . . . . . . . . . . . . . . . . . . . .89,98,99 6524 SSM. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .11,105 6525 Suppression_Enabled(I) . . . . . . . . . . . . . . . . . . . . . .36,132 6526 SwitchToSptDesired(S,G). . . . . . . . . . . . . . . . . . . . .28,28,43 6527 TIB. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7,14,26 6528 Triggered_Hello_Delay. . . . . . . . . . . . . . . . . . . . . 31,32,129 6529 t_joinsuppress . . . . . . . . . . . . . . . . . . . . . .63,64,67,69,74 6530 t_override . . . . . . . . . . . . . . . . . . . . . 63,67,72,77,132,133 6531 t_override_default . . . . . . . . . . . . . . . . . . . . . . . .36,129 6532 t_periodic . . . . . . . . . . . . . . . . . . . . . . . . .63,67,72,132 6533 t_suppressed . . . . . . . . . . . . . . . . . . . . .36,64,69,72,74,132 6534 Update_SPTbit(S,G,iif) . . . . . . . . . . . . . . . . . . . . . . 27,29 6535 UpstreamJPState(S,G) . . . . . . . . . . . . . . . . . . . . . . .27,107 6536 The IETF takes no position regarding the validity or scope of any 6537 Intellectual Property Rights or other rights that might be claimed to 6538 pertain to the implementation or use of the technology described in this 6539 document or the extent to which any license under such rights might or 6540 might not be available; nor does it represent that it has made any 6541 independent effort to identify any such rights. Information on the 6542 procedures with respect to rights in RFC documents can be found in BCP 6543 78 and BCP 79. 6545 Copies of IPR disclosures made to the IETF Secretariat and any 6546 assurances of licenses to be made available, or the result of an attempt 6547 made to obtain a general license or permission for the use of such 6548 proprietary rights by implementers or users of this specification can be 6549 obtained from the IETF on-line IPR repository at 6550 http://www.ietf.org/ipr. 6552 The IETF invites any interested party to bring to its attention any 6553 copyrights, patents or patent applications, or other proprietary rights 6554 that may cover technology that may be required to implement this 6555 standard. Please address the information to the IETF at ietf- 6556 ipr@ietf.org. 6558 13. Full Copyright Statement 6560 Copyright (C) The Internet Society (2004). This document is subject to 6561 the rights, licenses and restrictions contained in BCP 78, and except as 6562 set forth therein, the authors retain all their rights. 6564 This document and the information contained herein are provided on an 6565 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR 6566 IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET 6567 ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, 6568 INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE 6569 INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 6570 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.