idnits 2.17.1 draft-ietf-pim-dm-new-v2-05.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Looks like you're using RFC 2026 boilerplate. This must be updated to follow RFC 3978/3979, as updated by RFC 4748. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** The document seems to lack a 1id_guidelines paragraph about Internet-Drafts being working documents. ** The document seems to lack a 1id_guidelines paragraph about 6 months document validity. ** The document seems to lack a 1id_guidelines paragraph about the list of current Internet-Drafts. ** The document seems to lack a 1id_guidelines paragraph about the list of Shadow Directories. == No 'Intended status' indicated for this document; assuming Proposed Standard == The page length should not exceed 58 lines per page, but there was 5 longer pages, the longest (page 28) being 62 lines == It seems as if not all pages are separated by form feeds - found 55 form feeds but 110 pages Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** There are 8 instances of lines with control characters in the document. == 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 ** 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 -- however, there's a paragraph with a matching beginning. Boilerplate error? RFC 2119 keyword, line 184: '... that operations MUST be conducted in ...' RFC 2119 keyword, line 275: '...h an (S,G) entry MUST be maintained as...' RFC 2119 keyword, line 433: '...st, an RPF check MUST be performed to ...' RFC 2119 keyword, line 435: '...ts that fail the RPF check MUST NOT be...' RFC 2119 keyword, line 438: '...cannot be found MUST be discarded....' (329 more instances...) Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the RFC 3978 Section 5.4 Copyright Line does not match the current year -- 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 (December 2004) is 7071 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) == Unused Reference: '1' is defined on line 5143, but no explicit reference was found in the text == Unused Reference: '2' is defined on line 5146, but no explicit reference was found in the text == Unused Reference: '3' is defined on line 5149, but no explicit reference was found in the text == Unused Reference: '5' is defined on line 5158, but no explicit reference was found in the text == Unused Reference: '6' is defined on line 5161, but no explicit reference was found in the text == Unused Reference: '15' is defined on line 5193, but no explicit reference was found in the text ** Obsolete normative reference: RFC 2362 (ref. '4') (Obsoleted by RFC 4601, RFC 5059) ** Obsolete normative reference: RFC 2460 (ref. '5') (Obsoleted by RFC 8200) ** Downref: Normative reference to an Informational RFC: RFC 2715 (ref. '7') ** Obsolete normative reference: RFC 2434 (ref. '8') (Obsoleted by RFC 5226) -- Possible downref: Non-RFC (?) normative reference: ref. '9' ** Obsolete normative reference: RFC 2401 (ref. '10') (Obsoleted by RFC 4301) == Outdated reference: A later version (-12) exists of draft-ietf-pim-sm-v2-new-09 == Outdated reference: A later version (-07) exists of draft-ietf-ssm-arch-04 == Outdated reference: A later version (-09) exists of draft-ietf-pim-bidir-06 -- Obsolete informational reference (is this intentional?): RFC 3547 (ref. '17') (Obsoleted by RFC 6407) == Outdated reference: A later version (-12) exists of draft-ietf-pim-sm-bsr-03 Summary: 12 errors (**), 0 flaws (~~), 15 warnings (==), 5 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 Andrew Adams (NextHop Technolgies) 3 draft-ietf-pim-dm-new-v2-05.txt Jonathan Nicholas (ITT A/CD) 4 William Siadak (NextHop Technologies) 5 June 2004 6 Expires December 2004 8 Protocol Independent Multicast - Dense Mode (PIM-DM): 9 Protocol Specification (Revised) 11 Status of this Document 13 This document is an Internet Draft and is in full conformance with all 14 provisions of Section 10 of RFC 2026. 16 Internet Drafts are working documents of the Internet Engineering Task 17 Force (IETF), its areas, and its working groups. Note that other groups 18 may also distribute working documents as Internet Drafts. 20 Internet Drafts are draft documents valid for a maximum of six months 21 and may be updated, replaced, or obsoleted by other documents at any 22 time. It is inappropriate to use Internet Drafts as reference material 23 or to cite them other than as "work in progress." 25 The list of current Internet Drafts can be accessed at 26 http://www.ietf.org/ietf/lid-abstracts.txt. 28 The list of Internet Draft Shadow Directories can be accessed at 29 http://www.ietf.org/shadow.html. 31 This document is a product of the IETF PIM WG. Comments should be 32 addressed to the authors, or the WG's mailing list at pim@ietf.org. 34 Copyright Notice 36 Copyright (C) The Internet Society (2004). All Rights Reserved. 38 Abstract 40 This document specifies Protocol Independent Multicast - Dense Mode 41 (PIM-DM). PIM-DM is a multicast routing protocol that uses the 42 underlying unicast routing information base to flood multicast datagrams 43 to all multicast routers. Prune messages are used to prevent future 44 messages from propagating to routers with no group membership 45 information. 47 Table of Contents 49 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 4 50 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . 4 51 2.1. Definitions . . . . . . . . . . . . . . . . . . . . . . . . 4 52 2.2. Pseudocode Notation . . . . . . . . . . . . . . . . . . . . 5 53 3. PIM-DM Protocol Overview . . . . . . . . . . . . . . . . . . 5 54 4. Protocol Specification . . . . . . . . . . . . . . . . . . . 6 55 4.1. PIM Protocol State . . . . . . . . . . . . . . . . . . . . . 6 56 4.1.1. General Purpose State . . . . . . . . . . . . . . . . . . . 7 57 4.1.2. (S,G) State . . . . . . . . . . . . . . . . . . . . . . . . 7 58 4.1.3. State Summarization Macros . . . . . . . . . . . . . . . . . 8 59 4.2. Data Packet Forwarding Rules . . . . . . . . . . . . . . . . 10 60 4.3. Hello Messages . . . . . . . . . . . . . . . . . . . . . . . 10 61 4.3.1. Sending Hello Messages . . . . . . . . . . . . . . . . . . . 10 62 4.3.2. Receiving Hello Messages . . . . . . . . . . . . . . . . . . 11 63 4.3.3. Hello Message Hold Time . . . . . . . . . . . . . . . . . . 11 64 4.3.4. Handling Router Failures . . . . . . . . . . . . . . . . . . 11 65 4.3.5. Reducing Prune Propagation Delay on LANs . . . . . . . . . . 12 66 4.4. PIM-DM Prune, Join and Graft Messages . . . . . . . . . . . 13 67 4.4.1. Upstream Prune, Join and Graft Messages . . . . . . . . . . 13 68 4.4.1.1. Transitions from the Forwarding (F) State . . . . . . . . . 16 69 4.4.1.2. Transitions from the Pruned (P) State . . . . . . . . . . . 17 70 4.4.1.3. Transitions from the AckPending (AP) State . . . . . . . . . 18 71 4.4.2. Downstream Prune, Join and Graft Messages . . . . . . . . . 19 72 4.4.2.1. Transitions from the NoInfo State . . . . . . . . . . . . . 21 73 4.4.2.2. Transitions from the PrunePending (PP) State . . . . . . . . 22 74 4.4.2.3. Transitions from the Prune (P) State . . . . . . . . . . . . 23 75 4.5. State Refresh . . . . . . . . . . . . . . . . . . . . . . . 24 76 4.5.1. Forwarding of State Refresh Messages . . . . . . . . . . . . 24 77 4.5.2. State Refresh Message Origination . . . . . . . . . . . . . 25 78 4.5.2.1. Transitions from the NotOriginator (NO) State . . . . . . . 27 79 4.5.2.2. Transitions from the Originator (O) State . . . . . . . . . 27 80 4.6. PIM Assert Messages . . . . . . . . . . . . . . . . . . . . 28 81 4.6.1. Assert Metrics . . . . . . . . . . . . . . . . . . . . . . . 28 82 4.6.2. AssertCancel Messages . . . . . . . . . . . . . . . . . . . 29 83 4.6.3. Assert State Macros . . . . . . . . . . . . . . . . . . . . 29 84 4.6.4. (S,G) Assert Message State Machine . . . . . . . . . . . . . 29 85 4.6.4.1. Transitions from NoInfo State . . . . . . . . . . . . . . . 31 86 4.6.4.2. Transitions from Winner State . . . . . . . . . . . . . . . 32 87 4.6.4.3. Transitions from Loser State . . . . . . . . . . . . . . . . 33 88 4.6.5. Rationale for Assert Rules . . . . . . . . . . . . . . . . . 34 89 4.7. PIM Packet Formats . . . . . . . . . . . . . . . . . . . . . 35 90 4.7.1. PIM Header . . . . . . . . . . . . . . . . . . . . . . . . . 35 91 4.7.2. Encoded Unicast Address . . . . . . . . . . . . . . . . . . 36 92 4.7.3. Encoded Group Address . . . . . . . . . . . . . . . . . . . 36 93 4.7.4. Encoded Source Address . . . . . . . . . . . . . . . . . . . 37 94 4.7.5. Hello Message Format . . . . . . . . . . . . . . . . . . . . 38 95 4.7.5.1. Hello Hold Time Option . . . . . . . . . . . . . . . . . . . 39 96 4.7.5.2. LAN Prune Delay Option . . . . . . . . . . . . . . . . . . . 39 97 4.7.5.3. Generation ID Option . . . . . . . . . . . . . . . . . . . . 40 98 4.7.5.4. State Refresh Capable Option . . . . . . . . . . . . . . . . 40 99 4.7.6. Join/Prune Message Format . . . . . . . . . . . . . . . . . 40 100 4.7.7. Assert Message Format . . . . . . . . . . . . . . . . . . . 42 101 4.7.8. Graft Message Format . . . . . . . . . . . . . . . . . . . . 43 102 4.7.9. Graft Ack Message Format . . . . . . . . . . . . . . . . . . 43 103 4.7.10. State Refresh Message Format . . . . . . . . . . . . . . . . 44 104 4.8. PIM-DM Timers . . . . . . . . . . . . . . . . . . . . . . . 45 105 5. Protocol Interaction Considerations . . . . . . . . . . . . 48 106 5.1. PIM-SM Interactions . . . . . . . . . . . . . . . . . . . . 48 107 5.2. IGMP Interactions . . . . . . . . . . . . . . . . . . . . . 49 108 5.3. Source Specific Multicast (SSM) Interactions . . . . . . . . 49 109 5.4. Multicast Group Scope Boundary Interactions . . . . . . . . 49 110 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . 49 111 6.1. PIM Address Family . . . . . . . . . . . . . . . . . . . . . 49 112 6.2. PIM Hello Options . . . . . . . . . . . . . . . . . . . . . 50 113 7. Security Considerations. . . . . . . . . . . . . . . . . . . 50 114 7.1. Attacks Based on Forged Messages . . . . . . . . . . . . . . 50 115 7.2. Non-cryptographic Authentication Mechanisms . . . . . . . . 51 116 7.3. Authentication Using IPsec . . . . . . . . . . . . . . . . . 52 117 7.4. Denial of Service Attacks . . . . . . . . . . . . . . . . . 53 118 8. Authors' Addresses . . . . . . . . . . . . . . . . . . . . . 53 119 9. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . 53 120 10. References . . . . . . . . . . . . . . . . . . . . . . . . . 54 121 10.1. Normative References . . . . . . . . . . . . . . . . . . . . 54 122 10.2. Informative References . . . . . . . . . . . . . . . . . . . 54 123 11. Full Copyright Statement . . . . . . . . . . . . . . . . . . 55 124 1. Introduction 126 This specification defines a multicast routing algorithm for multicast 127 groups that are densely distributed across a network. This protocol 128 does not have a topology discovery mechanism often used by a unicast 129 routing protocol. It employs the same packet formats sparse mode PIM 130 (PIM-SM) uses. This protocol is called PIM - Dense Mode. The 131 foundation of this design was largely built on Deering's early work on 132 IP multicast routing [11]. 134 2. Terminology 136 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 137 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" are to be 138 interpreted as described in RFC 2119 and indicate requirement levels for 139 compliant PIM-DM implementations. 141 2.1. Definitions 143 Multicast Routing Information Base (MRIB) 144 This is the multicast topology table, which is typically derived from 145 the unicast routing table, or routing protocols such as MBGP that 146 carry multicast-specific topology information. PIM-DM uses the MRIB 147 to make decisions regarding RPF interfaces. 149 Tree Information Base (TIB) 150 This is the collection of state maintained by a PIM router and created 151 by receiving PIM messages and IGMP information from local hosts. It 152 essentially stores the state of all multicast distribution trees at 153 that router. 155 Reverse Path Forwarding (RPF) 156 RPF is a multicast forwarding mode where a data packet is accepted for 157 forwarding only if it is received on an interface used to reach the 158 source in unicast. 160 Upstream Interface 161 Interface towards the source of the datagram. Also known as the RPF 162 Interface. 164 Downstream Interface 165 All interfaces that are not the upstream interface, including the 166 router itself. 168 (S,G) Pair 169 Source S and destination group G associated with an IP packet. 171 2.2. Pseudocode Notation 173 We use set notation in several places in this specification. 175 A (+) B 176 is the union of two sets A and B. 178 A (-) B 179 are the elements of set A that are not in set B. 181 NULL 182 is the empty set or list. 184 Note that operations MUST be conducted in the order specified. This is 185 due to the fact that (-) is not a true difference operator because B is 186 not necessarily a subset of A. That is, A (+) B (-) C = A (-) C (+) B 187 is not a true statement unless C is a subset of both A and B. 189 In addition we use C-like syntax: 190 = denotes assignment of a variable. 191 == denotes a comparison for equality. 192 != denotes a comparison for inequality. 194 Braces { and } are used for grouping. 196 3. PIM-DM Protocol Overview 198 This section provides an overview of PIM-DM behavior. It is intended as 199 an introduction to how PIM-DM works, and is NOT definitive. For the 200 definitive specification, see Section 4 - Protocol Specification. 202 PIM-DM assumes that when a source starts sending, all downstream systems 203 want to receive multicast datagrams. Initially, multicast datagrams are 204 flooded to all areas of the network. PIM-DM uses RPF to prevent looping 205 of multicast datagrams while flooding. If some areas of the network do 206 not have group members, PIM-DM will prune off the forwarding branch by 207 instantiating prune state. 209 Prune state has a finite lifetime. When that lifetime expires, data 210 will again be forwarded down the previously pruned branch. 212 Prune state is associated with an (S,G) pair. When a new member for a 213 group G appears in a pruned area, a router can "graft" toward the source 214 S for the group, thereby turning the pruned branch back into a 215 forwarding branch. 217 The broadcast of datagrams followed by pruning of unwanted branches is 218 often referred to as a flood and prune cycle and is typical of dense 219 mode protocols. 221 In order to minimize repeated flooding of datagrams and subsequent 222 pruning associated with a particular (S,G) pair, PIM-DM uses a state 223 refresh message. This message is sent by the router(s) directly 224 connected to the source and is propagated throughout the network. When 225 received by a router on its RPF interface, the state refresh message 226 causes an existing prune state to be refreshed. 228 Compared with multicast routing protocols with built in topology 229 discovery mechanisms (e.g. DVMRP [12]) PIM-DM has a simplified design 230 and is not hard-wired into a specific topology discovery protocol. 231 However, such a simplification does incur more overhead by causing 232 flooding and pruning to occur on some links that could be avoided if 233 sufficient topology information were available, i.e. to decide whether 234 an interface leads to any downstream members of a particular group. 235 Additional overhead is chosen in favor of the simplification and 236 flexibility gained by not depending on a specific topology discovery 237 protocol. 239 PIM-DM differs from PIM-SM in two essential ways: 1) There are no 240 periodic joins transmitted, only explicitly triggered prunes and grafts. 241 2) There is no Rendezvous Point (RP). This is particularly important in 242 networks that cannot tolerate a single point of failure. (An RP is the 243 root of a shared multicast distribution tree. For more details see [4]). 245 4. Protocol Specification 247 The specification of PIM-DM is broken into several parts: 249 * Section 4.1 details the protocol state stored. 250 * Section 4.2 specifies the data packet forwarding rules. 251 * Section 4.3 specifies generation and processing of Hello messages. 252 * Section 4.4 specifies the Join, Prune and Graft generation and 253 processing rules. 254 * Section 4.5 specifies the State Refresh generation and forwarding 255 rules. 256 * Section 4.6 specifies the Assert generation and processing rules. 257 * Section 4.7 gives details on PIM-DM Packet Formats. 258 * Section 4.8 summarizes PIM-DM timers and their defaults. 260 4.1. PIM Protocol State 262 This section specifies all the protocol states that a PIM-DM 263 implementation should maintain in order to function correctly. We term 264 this state the Tree Information Base or TIB, as it holds the state of 265 all the multicast distribution trees at this router. In this 266 specification, we define PIM-DM mechanisms in terms of the TIB. 267 However, only a very simple implementation would actually implement 268 packet forwarding operations in terms of this state. Most 269 implementations will use this state to build a multicast forwarding 270 table, which would then be updated when the relevant state in the TIB 271 changes. 273 Unlike PIM-SM, PIM-DM does not maintain a keepalive timer associated 274 with each (S,G) route. Within PIM-DM, route and state information 275 associated with an (S,G) entry MUST be maintained as long as any timer 276 associated with that (S,G) entry is active. When no timer associated 277 with an (S,G) entry is active, all information concerning that (S,G) 278 route may be discarded. 280 Although we specify precisely the state to be kept, this does not mean 281 that an implementation of PIM-DM needs to hold the state in this form. 282 This is actually an abstract state definition, which is needed in order 283 to specify the router's behavior. A PIM-DM implementation is free to 284 hold whatever internal state it requires, and will still be conformant 285 with this specification so long as it results in the same externally 286 visible protocol behavior as an abstract router that holds the following 287 state. 289 4.1.1. General Purpose State 291 A router stores the following non-group-specific state: 293 For each interface: 294 Hello Timer (HT) 295 State Refresh Capable 296 LAN Delay Enabled 297 Propagation Delay (PD) 298 Override Interval (OI) 300 Neighbor State: 301 For each neighbor: 302 Information from neighbor's Hello 303 Neighbor's Gen ID. 304 Neighbor's LAN Prune Delay 305 Neighbor's Override Interval 306 Neighbor's State Refresh Capability 307 Neighbor Liveness Timer (NLT) 309 4.1.2. (S,G) State 311 For every source/group pair (S,G), a router stores the following state: 313 (S,G) state: 314 For each interface: 315 Local Membership: 316 State: One of {"NoInfo", "Include"} 318 PIM (S,G) Prune State: 319 State: One of {"NoInfo" (NI), "Pruned" (P), "PrunePending" (PP)} 320 Prune Pending Timer (PPT) 321 Prune Timer (PT) 323 (S,G) Assert Winner State: 324 State: One of {"NoInfo" (NI), "I lost Assert" (L), 325 "I won Assert" (W)} 326 Assert Timer (AT) 327 Assert winner's IP Address 328 Assert winner's Assert Metric 330 Upstream interface-specific: 331 Graft/Prune State: 332 State: One of {"NoInfo" (NI), "Pruned" (P), "Forwarding" (F), 333 "AckPending" (AP) } 334 GraftRetry Timer (GRT) 335 Override Timer (OT) 336 Prune Limit Timer (PLT) 338 Originator State: 339 Source Active Timer (SAT) 340 State Refresh Timer (SRT) 342 4.1.3. State Summarization Macros 344 Using the state defined above, the following "macros" are defined and 345 will be used in the descriptions of the state machines and pseudocode in 346 the following sections. 348 The most important macros are those defining the outgoing interface list 349 (or "olist") for the relevant state. 351 immediate_olist(S,G) = pim_nbrs (-) prunes(S,G) (+) 352 ( pim_include(*,G) (-) pim_exclude(S,G) ) (+) 353 pim_include(S,G) (-) lost_assert(S,G) (-) 354 boundary(G) 356 olist(S,G) = immediate_olist(S,G) (-) RPF_interface(S) 358 The macros pim_include(*,G) and pim_include(S,G) indicate the interfaces 359 to which traffic might be forwarded or not forwarded because of hosts 360 that are local members on those interfaces. 362 pim_include(*,G) = {all interfaces I such that: 363 local_receiver_include(*,G,I)} 364 pim_include(S,G) = {all interfaces I such that: 365 local_receiver_include(S,G,I)} 366 pim_exclude(S,G) = {all interfaces I such that: 367 local_receiver_exclude(S,G,I)} 369 The macro RPF_interface(S) returns the RPF interface for source S. That 370 is to say, it returns the interface used to reach S as indicated by the 371 MRIB. 373 The macro local_receiver_include(S,G,I) is true if the IGMP module or 374 other local membership mechanism has determined that there are local 375 members on interface I that desire to receive traffic sent specifically 376 by S to G. 378 The macro local_receiver_include(*,G,I) is true if the IGMP module or 379 other local membership mechanism has determined that there are local 380 members on interface I that desire to receive all traffic sent to G. 381 Note that this determination is expected to account for membership joins 382 initiated on or by the router. 384 The macro local_receiver_exclude(S,G,I) is true if 385 local_receiver_include(*,G,I) is true but none of the local members 386 desire to receive traffic from S. 388 The set pim_nbrs is the set of all interfaces on which the router has at 389 least one active PIM neighbor. 391 The set prunes(S,G) is the set of all interfaces on which the router has 392 received Prune(S,G) messages: 394 prunes(S,G) = {all interfaces I such that 395 DownstreamPState(S,G,I) is in Pruned state} 397 The set lost_assert(S,G) is the set of all interfaces on which the 398 router has lost an (S,G) Assert. 400 lost_assert(S,G) = {all interfaces I such that 401 lost_assert(S,G,I) == TRUE} 403 boundary(G) = {all interfaces I with an administratively scoped 404 boundary for group G} 406 The following pseudocode macro definitions are also used in many places 407 in the specification. Basically RPF' is the RPF neighbor towards a 408 source unless a PIM-DM Assert has overridden the normal choice of 409 neighbor. 411 neighbor RPF'(S,G) { 412 if ( I_Am_Assert_loser(S, G, RPF_interface(S) )) { 413 return AssertWinner(S, G, RPF_interface(S) ) 414 } else { 415 return MRIB.next_hop( S ) 416 } 417 } 419 The macro I_Am_Assert_loser(S, G, I) is true if the Assert state machine 420 (in section 4.6) for (S,G) on interface I is in the "I am Assert Loser" 421 state. 423 4.2. Data Packet Forwarding Rules 425 The PIM-DM packet forwarding rules are defined below in pseudocode. 427 iif is the incoming interface of the packet. 428 S is the source address of the packet. 429 G is the destination address of the packet (group address). 430 RPF_interface(S) is the interface the MRIB indicates would be used to 431 route packets to S. 433 First, an RPF check MUST be performed to determine whether the packet 434 should be accepted based on TIB state and the interface on which that 435 the packet arrived. Packets that fail the RPF check MUST NOT be 436 forwarded and the router will conduct an assert process for the (S,G) 437 pair specified in the packet. Packets for which a route to the source 438 cannot be found MUST be discarded. 440 If the RPF check has been passed, an outgoing interface list is 441 constructed for the packet. If this list is not empty, then the packet 442 MUST be forwarded to all listed interfaces. If the list is empty, then 443 the router will conduct a prune process for the (S,G) pair specified in 444 the packet. 446 On receipt on a data packet from S addressed to G on interface iif: 448 if (iif == RPF_interface(S) AND UpstreamPState(S,G) != Pruned) { 449 oiflist = olist(S,G) 450 } else { 451 oiflist = NULL 452 } 453 forward packet on all interfaces in oiflist 455 This pseudocode employs the following "macro" definition: 457 UpstreamPState(S,G) is the state of the Upstream(S,G) state machine in 458 section 4.4.1. 460 4.3. Hello Messages 462 This section describes the generation and processing of Hello messages. 464 4.3.1. Sending Hello Messages 466 PIM-DM uses Hello messages to detect other PIM routers. Hello messages 467 are sent periodically on each PIM enabled interface. Hello messages are 468 multicast to the ALL-PIM-ROUTERS group. When PIM is enabled on an 469 interface or a router first starts, the Hello Timer (HT) MUST be set to 470 random value between 0 and Triggered_Hello_Delay. This prevents 471 synchronization of Hello messages if multiple routers are powered on 472 simultaneously. 474 After the initial Hello message, a Hello message MUST be sent every 475 Hello_Period. A single Hello timer MAY be used to trigger sending 476 Hello messages on all active interfaces. The Hello Timer SHOULD NOT be 477 reset except when it expires. 479 4.3.2. Receiving Hello Messages 481 When a Hello message is received, the receiving router SHALL record the 482 receiving interface, the sender and any information contained in 483 recognized options. This information is retained for a number of 484 seconds in the Hold Time field of the Hello Message. If a new Hello 485 message is received from a particular neighbor N, the Neighbor Liveness 486 Timer (NLT(N,I)) MUST be reset to the newly received Hello Holdtime. If 487 a Hello message is received from a new neighbor, the receiving router 488 SHOULD send its own Hello message after a random delay between 0 and 489 Triggered_Hello_Delay. 491 4.3.3. Hello Message Hold Time 493 The Hold Time in the Hello Message should be set to a value that can 494 reasonably be expected to keep the Hello active until a new Hello 495 message is received. On most links, this will be 3.5 times the value of 496 Hello_Period. 498 If the Hold Time is set to '0xffff', the receiving router MUST NOT time 499 out that Hello message. This feature might be used for on-demand links 500 to avoid keeping the link up with periodic Hello messages. 502 If a Hold Time of '0' is received, the corresponding neighbor state is 503 expired immediately. When a PIM router takes an interface down or 504 changes IP address, a Hello message with a zero Hold Time SHOULD be sent 505 immediately (with the old IP address if the IP address is changed) to 506 cause any PIM neighbors to remove the old information immediately. 508 4.3.4. Handling Router Failures 510 If a Hello message is received from an active neighbor with a different 511 Generation ID (GenID), the neighbor has restarted and may not contain 512 the correct (S,G) state. A Hello message SHOULD be sent after a random 513 delay between 0 and Triggered_Hello_Delay (see 4.8) before any other 514 messages are sent. If the neighbor is downstream, the router MAY 515 replay the last State Refresh message for any (S,G) pairs for which it 516 is the Assert Winner indicating Prune and Assert status to the 517 downstream router. These State Refresh messages SHOULD be sent out 518 immediately after the Hello message. If the neighbor is the upstream 519 neighbor for an (S,G) entry, the router MAY cancel its Prune Limit 520 Timer to permit sending a prune and reestablishing a Pruned state in the 521 upstream router. 523 Upon startup, a router MAY use any State Refresh messages received 524 within Hello_Period of its first Hello message on an interface to 525 establish state information. The State Refresh source will be the 526 RPF'(S), and Prune status for all interfaces will be set according to 527 the Prune Indicator bit in the State Refresh message. If the Prune 528 Indicator is set, the router SHOULD set the PruneLimitTimer to 529 Prune_Holdtime and set the PruneTimer on all downstream interfaces to 530 the State Refresh's Interval times two. The router SHOULD then 531 propagate the State Refresh as described in section 4.5.1. 533 4.3.5. Reducing Prune Propagation Delay on LANs 535 If all routers on a LAN support the LAN Prune Delay option, then the PIM 536 routers on that LAN will use the values received to adjust their 537 J/P_Override_Interval on that interface and the interface is LAN Delay 538 Enabled. Briefly, to avoid synchronization of Prune Override (Join) 539 messages when multiple downstream routers share a multi-access link, 540 sending of such messages is delayed by a small random amount of time. 541 The period of randomization is configurable and has a default value of 3 542 seconds. 544 Each router on the LAN expresses its view of the amount of randomization 545 necessary in the Override Interval field of the LAN Prune Delay option. 546 When all routers on a LAN use the LAN Prune Delay Option, all routers on 547 the LAN MUST set their Override_Interval to the largest Override value 548 on the LAN. 550 The LAN Delay inserted by a router in the LAN Prune Delay option 551 expresses the expected message propagation delay on the link and SHOULD 552 be configurable by the system administrator. When all routers on a link 553 use the LAN Prune Delay Option, all routers on the LAN MUST set 554 Propagation Delay to the largest LAN Delay on the LAN. 556 PIM implementers should enforce a lower bound on the permitted values 557 for this delay to allow for scheduling and processing delays within 558 their router. Such delays may cause received messages to be processed 559 later as well as triggered messages to be sent later than intended. 560 Setting this LAN Prune Delay to too low a value may result in temporary 561 forwarding outages because a downstream router will not be able to 562 override a neighbor's prune message before the upstream neighbor stops 563 forwarding. 565 4.4. PIM-DM Prune, Join and Graft Messages 567 This section describes the generation and processing of PIM-DM Join, 568 Prune and Graft messages. Prune messages are sent towards the upstream 569 neighbor for S to indicate that traffic from S addressed to group G is 570 not desired. In the case of two downstream routers A and B, where A 571 wishes to continue receiving data and B does not, A will send a Join in 572 response to B's Prune to override the Prune. This is the only situation 573 in PIM-DM in which a Join message is used. Finally, a Graft message is 574 used to re-join a previously pruned branch to the delivery tree. 576 4.4.1. Upstream Prune, Join and Graft Messages 578 The Upstream(S,G) state machine for sending Prune, Graft and Join 579 messages is given below. There are three states. 581 Forwarding (F) 582 This is the starting state of the Upsteam(S,G) state machine. The 583 state machine is in this state if it just started or if 584 oiflist(S,G) != NULL. 586 Pruned(P) 587 The set, olist(S,G), is empty. The router will not forward data 588 from S addressed to group G. 590 AckPending(AP) 591 The router was in the Pruned(P) state but a transition has occurred 592 in the Downstream(S,G) state machine for one of this (S,G) entry's 593 outgoing interfaces indicating that traffic from S addressed to G 594 should again be forwarded. A Graft message has been sent to RPF'(S) 595 but a Graft Ack message has not yet been received. 597 In addition there are three state-machine-specific timers: 599 GraftRetry Timer (GRT(S,G)) 600 This timer is set when a Graft is sent upstream. If a corresponding 601 GraftAck is not received before the timer expires, then another 602 Graft is sent and the GraftRetry Timer is reset. The timer is 603 stopped when a Graft Ack message is received. This timer is normally 604 set to Graft_Retry_Period (see 4.8). 606 Override Timer (OT(S,G)) 607 This timer is set when a Prune(S,G) is received on the upstream 608 interface where olist(S,G) != NULL. When the timer expires, a 609 Join(S,G) message is sent on the upstream interface. This timer is 610 normally set to t_override (see 4.8). 612 Prune Limit Timer (PLT(S,G)) 613 This timer is used to rate-limit Prunes on a LAN. It is only used 614 when the Upstream(S,G) state machine is in the Pruned state. A Prune 615 cannot be sent if this timer is running. This timer is normally set 616 to t_limit (see 4.8). 618 +-------------+ +-------------+ 619 | | olist == NULL | | 620 | Forward |----------------------->| Pruned | 621 | | | | 622 +-------------+ +-------------+ 623 ^ | ^ | 624 | | | | 625 | |RPF`(S) Changes olist == NULL| | 626 | | | | 627 | | +-------------+ | | 628 | +-------->| |----------+ | 629 | | AckPending | | 630 +-------------| |<-------------+ 631 Rcv GraftAck OR +-------------+ olist != NULL 632 Rcv State Refresh 633 With (P==0) OR 634 S Directly Connect 636 Figure 1: Upstream Interface State Machine 638 In tabular form, the state machine is defined as follows: 640 +-------------------------------+--------------------------------------+ 641 | | Previous State | 642 | +------------+------------+------------+ 643 | Event | Forwarding | Pruned | AckPending | 644 +-------------------------------+------------+------------+------------+ 645 | Data packet arrives on | ->P Send | ->P Send | N/A | 646 | RPF_Interface(S) AND | Prune(S,G) | Prune(S,G) | | 647 | olist(S,G) == NULL AND |Set PLT(S,G)|Set PLT(S,G)| | 648 | PLT(S,G) not running | | | | 649 +-------------------------------+------------+------------+------------+ 650 | State Refresh(S,G) received | ->F Set | ->P Reset |->AP Set | 651 | from RPF`(S) AND | OT(S,G) | PLT(S,G) | OT(S,G) | 652 | Prune Indicator == 1 | | | | 653 +-------------------------------+------------+------------+------------+ 654 | State Refresh(S,G) received | ->F | ->P Send |->F Cancel | 655 | from RPF`(S) AND | | Prune(S,G) | GRT(S,G) | 656 | Prune Indicator == 0 AND | |Set PLT(S,G)| | 657 | PLT(S,G) not running | | | | 658 +-------------------------------+------------+------------+------------+ 659 | See Join(S,G) to RPF'(S) | ->F Cancel | ->P |->AP Cancel | 660 | | OT(S,G) | | OT(S,G) | 661 +-------------------------------+------------+------------+------------+ 662 | See Prune(S,G) | ->F Set | ->P |->AP Set | 663 | | OT(S,G) | | OT(S,G) | 664 +-------------------------------+------------+------------+------------+ 665 | OT(S,G) Expires | ->F Send | N/A |->AP Send | 666 | | Join(S,G) | | Join(S,G) | 667 +-------------------------------+------------+------------+------------+ 668 +-------------------------------+--------------------------------------+ 669 | | Previous State | 670 | +------------+------------+------------+ 671 | Event | Forwarding | Pruned | AckPending | 672 +-------------------------------+------------+------------+------------+ 673 | olist(S,G)->NULL | ->P Send | N/A |->P Send | 674 | | Prune(S,G) | | Prune(S,G) | 675 | |Set PLT(S,G)| |Set PLT(S,G)| 676 | | | | Cancel | 677 | | | | GRT(S,G) | 678 +-------------------------------+------------+------------+------------+ 679 | olist(S,G)->non-NULL | N/A | ->AP Send | N/A | 680 | | | Graft(S,G) | | 681 | | |Set GRT(S,G)| | 682 +-------------------------------+------------+------------+------------+ 683 | RPF'(S) Changes AND | ->AP Send | ->AP Send |->AP Send | 684 | olist(S,G) != NULL | Graft(S,G) | Graft(S,G) | Graft(S,G) | 685 | |Set GRT(S,G)|Set GRT(S,G)|Set GRT(S,G)| 686 +-------------------------------+------------+------------+------------+ 687 | RPF'(S) Changes AND | ->P | ->P Cancel |->P Cancel | 688 | olist(S,G) == NULL | | PLT(S,G) | GRT(S,G) | 689 +-------------------------------+------------+------------+------------+ 690 | S becomes directly connected | ->F | ->P |->F Cancel | 691 | | | | GRT(S,G) | 692 +-------------------------------+------------+------------+------------+ 693 | GRT(S,G) Expires | N/A | N/A |->AP Send | 694 | | | | Graft(S,G) | 695 | | | |Set GRT(S,G)| 696 +-------------------------------+------------+------------+------------+ 697 | Receive GraftAck(S,G) from | ->F | ->P |->F Cancel | 698 | RPF'(S) | | | GRT(S,G) | 699 +-------------------------------+------------+------------+------------+ 701 The transition event "RcvGraftAck(S,G)" implies receiving a Graft Ack 702 message targeted to this router's address on the incoming interface for 703 the (S,G) entry. If the destination address is not correct, the state 704 transitions in this state machine must not occur. 706 4.4.1.1. Transitions from the Forwarding (F) State 708 When the Upstream(S,G) state machine is in the Forwarding (F) state, the 709 following events may trigger a transition: 711 Data Packet arrives on RPF_Interface(S) AND olist(S,G) == NULL AND S 712 NOT directly connected 713 The Upstream(S,G) state machine MUST transition to the Pruned (P) 714 state, send a Prune(S,G) to RPF'(S) and set PLT(S,G) to t_limit 715 seconds. 717 State Refresh(S,G) Received from RPF'(S) 718 The Upstream(S,G) state machine remains in a Forwarding state. If 719 the received State Refresh has the Prune Indicator bit set to one, 720 this router must override the upstream router's Prune state after a 721 short random interval. If OT(S,G) is not running and the Prune 722 Indicator bit equals one, the router MUST set OT(S,G) to t_override 723 seconds. 725 See Join(S,G) to RPF'(S) 726 This event is only relevant if RPF_interface(S) is a shared medium. 727 This router sees another router on RPF_interface(S) send a Join(S,G) 728 to RPF'(S,G). If the OT(S,G) is running, then it means that the 729 router had scheduled a Join to override a previously received Prune. 730 Another router has responded more quickly with a Join and so the 731 local router SHOULD cancel its OT(S,G), if it is running. The 732 Upstream(S,G) state machine remains in the Forwarding (F) state. 734 See Prune(S,G) AND S NOT directly connected 735 This event is only relevant if RPF_interface(S) is a shared medium. 736 This router sees another router on RPF_interface(S) send a 737 Prune(S,G). As this router is in Forwarding state, it must 738 override the Prune after a short random interval. If OT(S,G) is not 739 running, the router MUST set OT(S,G) to t_override seconds. The 740 Upstream(S,G) state machine remains in Forwarding (F) state. 742 OT(S,G) Expires AND S NOT directly connected 743 The OverrideTimer (OT(S,G)) expires. The router MUST send a 744 Join(S,G) to RPF'(S) to override a previously detected prune. The 745 Upstream(S,G) state machine remains in the Forwarding (F) state. 747 olist(S,G) -> NULL AND S NOT directly connected 748 The Upstream(S,G) state machine MUST transition to the Pruned (P) 749 state, send a Prune(S,G) to RPF'(S) and set PLT(S,G) to t_limit 750 seconds. 752 RPF'(S) Changes AND olist(S,G) is non-NULL AND S NOT directly 753 connected 754 Unicast routing or Assert state causes RPF'(S) to change, including 755 changes to RPF_Interface(S). The Upstream(S,G) state machine MUST 756 transition to the AckPending (AP) state, unicast a Graft to the new 757 RPF'(S) and set the GraftRetry Timer (GRT(S,G)) to 758 Graft_Retry_Period. 760 RPF'(S) Changes AND olist(S,G) is NULL 761 Unicast routing or Assert state causes RPF'(S) to change, including 762 changes to RPF_Interface(S). The Upstream(S,G) state machine MUST 763 transition to the Pruned (P) state. 765 4.4.1.2. Transitions from the Pruned (P) State 767 When the Upstream(S,G) state machine is in the Pruned (P) state, the 768 following events may trigger a transition: 770 Data arrives on RPF_interface(S) AND PLT(S,G) not running AND S NOT 771 directly connected 772 Either another router on the LAN desires traffic from S addressed to 773 G or a previous Prune was lost. In order to prevent generating a 774 Prune(S,G) in response to every data packet, the PruneLimit Timer 775 (PLT(S,G)) is used. Once the PLT(S,G) expires, the router needs to 776 send another prune in response to a data packet not received 777 directly from the source. A Prune(S,G) MUST be sent to RPF'(S) and 778 the PLT(S,G) MUST be set to t_limit. 780 State Refresh(S,G) Received from RPF'(S) 781 The Upstream(S,G) state machine remains in a Pruned state. If the 782 State Refresh has its Prune Indicator bit set to zero and PLT(S,G) 783 is not running, a Prune(S,G) MUST be sent to RPF'(S) and the 784 PLT(S,G) MUST be set to t_limit. If the State Refresh has its Prune 785 Indicator bit set to one, the router MUST reset PLT(S,G) to t_limit. 787 See Prune(S,G) to RPF'(S) 788 A Prune(S,G) is seen on RPF_interface(S) to RPF'(S). The 789 Upstream(S,G) state machine stays in the Pruned (P) state. The 790 router MAY reset its PLT(S,G) to the value in the Holdtime field of 791 the received message if greater than the current value of the 792 PLT(S,G). 794 olist(S,G)->non-NULL AND S NOT directly connected 795 The set of interfaces defined by the olist(S,G) macro becomes 796 non-empty indicating traffic from S addressed to group G must be 797 forwarded. The Upstream(S,G) state machine MUST cancel PLT(S,G), 798 transition to the AckPending (AP) state and unicast a Graft message 799 to RPF'(S). The Graft Retry Timer (GRT(S,G)) MUST be set to 800 Graft_Retry_Period. 802 RPF'(S) Changes AND olist(S,G) == non-NULL AND S NOT directly 803 connected 804 Unicast routing or Assert state causes RPF'(S) to change, including 805 changes to RPF_Interface(S). The Upstream(S,G) state machine MUST 806 cancel PLT(S,G), transition to the AckPending (AP) state, send a 807 Graft unicast to the new RPF'(S) and set the GraftRetry Timer 808 (GRT(S,G)) to Graft_Retry_Period. 810 RPF'(S) Changes AND olist(S,G) == NULL AND S NOT directly connected 811 Unicast routing or Assert state causes RPF'(S) to change, including 812 changes to RPF_Interface(S). The Upstream(S,G) state machine stays 813 in the Pruned (P) state and MUST cancel the PLT(S,G) timer. 815 S becomes directly connected 816 Unicast routing changed so that S is directly connected. The 817 Upstream(S,G) state machine remains in the Pruned (P) state. 819 4.4.1.3. Transitions from the AckPending (AP) State 821 When the Upstream(S,G) state machine is in the AckPending (AP) state, 822 the following events may trigger a transition: 824 State Refresh(S,G) Received from RPF'(S) with Prune Indicator == 1 825 The Upstream(S,G) state machine remains in an AckPending state. The 826 router must override the upstream router's Prune state after a short 827 random interval. If OT(S,G) is not running and the Prune Indicator 828 bit equals one, the router MUST set OT(S,G) to t_override seconds. 830 State Refresh(S,G) Received from RPF'(S) with Prune Indicator == 0 831 The router MUST cancel its GraftRetry Timer (GRT(S,G)) and 832 transition to the Forwarding (F) state. 834 See Join(S,G) to RPF'(S,G) 835 This event is only relevant if RPF_interface(S) is a shared medium. 836 This router sees another router on RPF_interface(S) send a Join(S,G) 837 to RPF'(S,G). If the OT(S,G) is running, then it means that the 838 router had scheduled a Join to override a previously received Prune. 839 Another router has responded more quickly with a Join and so the 840 local router SHOULD cancel its OT(S,G), if it is running. The 841 Upstream(S,G) state machine remains in the AckPending (AP) state. 843 See Prune(S,G) 844 This event is only relevant if RPF_interface(S) is a shared medium. 845 This router sees another router on RPF_interface(S) send a 846 Prune(S,G). As this router is in AckPending (AP) state, it must 847 override the Prune after a short random interval. If OT(S,G) is not 848 running, the router MUST set OT(S,G) to t_override seconds. The 849 Upstream(S,G) state machine remains in AckPending (AP) state. 851 OT(S,G) Expires 852 The OverrideTimer (OT(S,G)) expires. The router MUST send a 853 Join(S,G) to RPF'(S). The Upstream(S,G) state machine remains in 854 the AckPending (AP) state. 856 olist(S,G) -> NULL 857 The set of interfaces defined by the olist(S,G) macro becomes null 858 indicating traffic from S addressed to group G should no longer be 859 forwarded. The Upstream(S,G) state machine MUST transition to the 860 Pruned (P) state. A Prune(S,G) MUST be multicast to the 861 RPF_interface(S) with RPF'(S) named in the upstream neighbor field. 862 The GraftRetry Timer (GRT(S,G)) MUST be cancelled and PLT(S,G) MUST 863 be set to t_limit seconds. 865 RPF'(S) Changes AND olist(S,G) does not become NULL AND S NOT directly 866 connected 867 Unicast routing or Assert state causes RPF'(S) to change, including 868 changes to RPF_Interface(S). The Upstream(S,G) state machine stays 869 in the AckPending (AP) state. A Graft MUST be unicast to the new 870 RPF'(S) and the GraftRetry Timer (GRT(S,G)) reset to 871 Graft_Retry_Period. 873 RPF'(S) Changes AND olist(S,G) == NULL AND S NOT directly connected 874 Unicast routing or Assert state causes RPF'(S) to change, including 875 changes to RPF_Interface(S). The Upstream(S,G) state machine MUST 876 transition to the Pruned (P) state. The GraftRetry Timer (GRT(S,G)) 877 MUST be cancelled. 879 S becomes directly connected 880 Unicast routing has changed so that S is directly connected. The 881 GraftRetry Timer MUST be cancelled and the Upstream(S,G) state 882 machine MUST transition to the Forwarding(F) state. 884 GRT(S,G) Expires 885 The GraftRetry Timer (GRT(S,G)) expires for this (S,G) entry. The 886 Upstream(S,G) state machine stays in the AckPending (AP) state. 887 Another Graft message for (S,G) SHOULD be unicasted to RPF'(S) and 888 the GraftRetry Timer (GRT(S,G)) reset to Graft_Retry_Period. It is 889 RECOMMENDED that the router retry a configured number of times 890 before ceasing retries. 892 See GraftAck(S,G) from RPF'(S) 893 A GraftAck is received from RPF'(S). The GraftRetry Timer MUST be 894 cancelled and the Upstream(S,G) state machine MUST transition to the 895 Forwarding(F) state. 897 4.4.2 Downstream Prune, Join and Graft Messages 899 The Prune(S,G) Downstream state machine for receiving Prune, Join and 900 Graft messages on interface I is given below. This state machine MUST 901 always be in the NoInfo state on the upstream interface. It contains 902 three states. 904 NoInfo(NI) 905 The interface has no (S,G) Prune state and neither the Prune timer 906 (PT(S,G,I)) nor the PrunePending timer ((PPT(S,G,I)) is running. 908 PrunePending(PP) 909 The router has received a Prune(S,G) on this interface from a 910 downstream neighbor and is waiting to see whether the prune will be 911 overridden by another downstream router. For forwarding purposes, 912 the PrunePending state functions exactly like the NoInfo state. 914 Pruned(P) 915 The router has received a Prune(S,G) on this interface from a 916 downstream neighbor and the Prune was not overridden. Data from S 917 addressed to group G is no longer being forwarded on this interface. 919 In addition there are two timers: 921 PrunePending Timer (PPT(S,G,I)) 922 This timer is set when a valid Prune(S,G) is received. Expiry of 923 the PrunePending Timer (PPT(S,G,I)) causes the interface to 924 transition to the Pruned state. 926 Prune Timer (PT(S,G,I)) 927 This timer is set when the PrunePending Timer (PT(S,G,I)) expires. 928 Expiry of the Prune Timer (PT(S,G,I)) causes the interface to 929 transition to the NoInfo (NI) state, thereby allowing data from S 930 addressed to group G to be forwarded on the interface. 932 +-------------+ +-------------+ 933 | | PPT Expires | | 934 |PrunePending |----------------------->| Pruned | 935 | | | | 936 +-------------+ +-------------+ 937 | ^ | 938 | | | 939 | |Rcv Prune | 940 | | | 941 | | +-------------+ | 942 | +---------| | | 943 | | NoInfo |<-------------+ 944 +------------>| | Rcv Join/Graft OR 945 Rcv Join/Graft OR +-------------+ PT Expires OR 946 RPF_Interface(S)->I RPF_Interface(S)->I 948 Figure 2: Downstream Interface State Machine 950 In tabular form, the state machine is: 952 +-------------------------------+--------------------------------------+ 953 | | Previous State | 954 + +------------+------------+------------+ 955 | Event | No Info | PrunePend | Pruned | 956 +-------------------------------+------------+------------+------------+ 957 | Receive Prune(S,G) |->PP Set |->PP |->P Reset | 958 | | PPT(S,G,I) | | PT(S,G,I) | 959 +-------------------------------+------------+------------+------------+ 960 | Receive Join(S,G) |->NI |->NI Cancel |->NI Cancel | 961 | | | PPT(S,G,I) | PT(S,G,I) | 962 +-------------------------------+------------+------------+------------+ 963 | Receive Graft(S,G) |->NI Send |->NI Send |->NI Send | 964 | | GraftAck | GraftAck | GraftAck | 965 | | | Cancel | Cancel | 966 | | | PPT(S,G,I) | PT(S,G,I) | 967 +-------------------------------+------------+------------+------------+ 968 | PPT(S,G) Expires | N/A |->P Set | N/A | 969 | | | PT(S,G,I) | | 970 +-------------------------------+------------+------------+------------+ 971 | PT(S,G) Expires | N/A | N/A |->NI | 972 +-------------------------------+------------+------------+------------+ 973 | RPF_Interface(S) becomes I |->NI |->NI Cancel |->NI Cancel | 974 | | | PPT(S,G,I) | PT(S,G,I) | 975 +-------------------------------+------------+------------+------------+ 976 | Send State Refresh(S,G) out I |->NI |->PP |->P Reset | 977 | | | | PT(S,G,I) | 978 +-------------------------------+------------+------------+------------+ 980 The transition events "Receive Graft(S,G)", "Receive Prune(S,G)" and 981 "Receive Join(S,G)" denote receiving a Graft, Prune or Join message in 982 which this router's address on I is contained in the message's upstream 983 neighbor field. If the upstream neighbor field does not match this 984 router's address on I, then these state transitions in this state 985 machine must not occur. 987 4.4.2.1. Transitions from the NoInfo State 989 When the Prune(S,G) Downstream state machine is in the NoInfo (NI) 990 state, the following events may trigger a transition: 992 Receive Prune(S,G) 993 A Prune(S,G) is received on interface I with the upstream neighbor 994 field set to the router's address on I. The Prune(S,G) Downstream 995 state machine on interface I MUST transition to the PrunePending 996 (PP) state. The PrunePending Timer (PPT(S,G,I)) MUST be set to 997 J/P_Override_Interval if the router has more than one neighbor on I. 998 If the router has only one neighbor on interface I, then it SHOULD 999 set the PPT(S,G,I) to zero, effectively transitioning immediately to 1000 the Pruned (P) state. 1002 Receive Graft(S,G) 1003 A Graft(S,G) is received on the interface I with the upstream 1004 neighbor field set to the router's address on I. The Prune(S,G) 1005 Downstream state machine on interface I stays in the NoInfo (NI) 1006 state. A GraftAck(S,G) MUST be unicasted to the originator of the 1007 Graft(S,G) message. 1009 4.4.2.2. Transitions from the PrunePending (PP) State 1011 When the Prune(S,G) downstream state machine is in the PrunePending (PP) 1012 state, the following events may trigger a transition. 1014 Receive Join(S,G) 1015 A Join(S,G) is received on interface I with the upstream neighbor 1016 field set to the router's address on I. The Prune(S,G) Downstream 1017 state machine on interface I MUST transition to the NoInfo (NI) 1018 state. The PrunePending Timer (PPT(S,G,I)) MUST be cancelled. 1020 Receive Graft(S,G) 1021 A Graft(S,G) is received on interface I with the upstream neighbor 1022 field set to the router's address on I. The Prune(S,G) Downstream 1023 state machine on interface I MUST transition to the NoInfo (NI) 1024 state and MUST unicast a Graft Ack message to the Graft originator. 1025 The PrunePending Timer (PPT(S,G,I)) MUST be cancelled. 1027 PPT(S,G,I) Expires 1028 The PrunePending Timer (PPT(S,G,I)) expires indicating that no 1029 neighbors have overridden the previous Prune(S,G) message. The 1030 Prune(S,G) Downstream state machine on interface I MUST transition 1031 to the Pruned (P) state. The Prune Timer (PT(S,G,I)) is started and 1032 MUST be initialized to the received Prune_Hold_Time minus 1033 J/P_Override_Interval. A PruneEcho(S,G) MUST be sent on I if I has 1034 more than one PIM neighbor. A PruneEcho(S,G) is simply a Prune(S,G) 1035 message multicast by the upstream router to a LAN with itself as the 1036 Upstream Neighbor. Its purpose is to add additional reliability so 1037 that if a Join that should have overridden the Prune is lost locally 1038 on the LAN, then the PruneEcho(S,G) may be received and trigger a 1039 new Join message . A PruneEcho(S,G) is OPTIONAL on an interface 1040 with only one PIM neighbor. In addition, the router MUST evaluate 1041 any possible transitions in the Upstream(S,G) state machine. 1043 RPF_Interface(S) becomes interface I 1044 The upstream interface for S has changed. The Prune(S,G) Downstream 1045 state machine on interface I MUST transition to the NoInfo (NI) 1046 state. The PrunePending Timer (PPT(S,G,I)) MUST be cancelled. 1048 4.4.2.3. Transitions from the Prune (P) State 1050 When the Prune(S,G) Downstream state machine is in the Pruned (P) state, 1051 the following events may trigger a transition. 1053 Receive Prune(S,G) 1054 A Prune(S,G) is received on the interface I with the upstream 1055 neighbor field set to the router's address on I. The Prune(S,G) 1056 Downstream state machine on interface I remains in the Pruned (P) 1057 state. The Prune Timer (PT(S,G,I)) SHOULD be reset to the holdtime 1058 contained in the Prune(S,G) message if it is greater than the 1059 current value. 1061 Receive Join(S,G) 1062 A Join(S,G) is received on the interface I with the upstream 1063 neighbor field set to the router's address on I. The Prune(S,G) 1064 downstream state machine on interface I MUST transition to the 1065 NoInfo (NI) state. The Prune Timer (PT(S,G,I)) MUST be cancelled. 1066 The router MUST evaluate any possible transitions in the 1067 Upstream(S,G) state machine. 1069 Receive Graft(S,G) 1070 A Graft(S,G) is received on interface I with the upstream neighbor 1071 field set to the router's address on I. The Prune(S,G) Downstream 1072 state machine on interface I MUST transition to the NoInfo (NI) 1073 state and send a Graft Ack back to the Graft's source. The Prune 1074 Timer (PT(S,G,I)) MUST be cancelled. The router MUST evaluate any 1075 possible transitions in the Upstream(S,G) state machine. 1077 PT(S,G,I) Expires 1078 The Prune Timer (PT(S,G,I)) expires indicating that it is again time 1079 to flood data from S addressed to group G onto interface I. The 1080 Prune(S,G) Downstream state machine on interface I MUST transition 1081 to the NoInfo (NI) state. The router MUST evaluate any possible 1082 transitions in the Upstream(S,G) state machine. 1084 RPF_Interface(S) becomes interface I 1085 The upstream interface for S has changed. The Prune(S,G) Downstream 1086 state machine on interface I MUST transition to the NoInfo (NI) 1087 state. The PruneTimer (PT(S,G,I)) MUST be cancelled. 1089 Send State Refresh(S,G) out interface I 1090 The router has refreshed the Prune(S,G) state on interface I. The 1091 router MUST reset the Prune Timer (PT(S,G,I)) to the Holdtime from 1092 an active Prune received on interface I. The Holdtime used SHOULD 1093 be the largest active one, but MAY be the most recently received 1094 active Prune Holdtime. 1096 4.5. State Refresh 1098 This section describes the major portions of the state refresh 1099 mechanism. 1101 4.5.1. Forwarding of State Refresh Messages 1103 When a State Refresh message, SRM, is received, it is forwarded 1104 according to the following pseudo-code. 1106 if (iif != RPF_interface(S)) 1107 return; 1108 if (RPF'(S) != srcaddr(SRM)) 1109 return; 1110 if (StateRefreshRateLimit(S,G) == TRUE) 1111 return; 1113 for each interface I in pim_nbrs { 1114 if (TTL(SRM) == 0 OR (TTL(SRM) - 1) < Threshold(I)) 1115 continue; /* Out of TTL, skip this interface */ 1116 if (boundary(I,G)) 1117 continue; /* This interface is scope boundary, skip it */ 1118 if (I == iif) 1119 continue; /* This is the incoming interface, skip it */ 1120 if (lost_assert(S,G,I) == TRUE) 1121 continue; /* Let the Assert Winner do State Refresh */ 1123 Copy SRM to SRM'; /* Make a copy of SRM to forward */ 1125 if (I contained in prunes(S,G)) { 1126 set Prune Indicator bit of SRM' to 1; 1128 if StateRefreshCapable(I) == TRUE 1129 set PT(S,G) to largest active holdtime read from a Prune message 1130 accepted on I; 1132 } else { 1133 set Prune Indicator bit of SRM' to 0; 1134 } 1136 set srcaddr(SRM') to my_addr(I); 1137 set TTL of SRM' to TTL(SRM) - 1; 1138 set metric of SRM' to metric of unicast route used to reach S; 1139 set pref of SRM' to preference of unicast route used to reach S; 1140 set mask of SRM' to mask of route used to reach S; 1141 if (AssertState == NoInfo) { 1142 set Assert Override of SRM' to 1; 1143 } else { 1144 set Assert Override of SRM' to 0; 1145 } 1147 transmit SRM' on I; 1148 } 1150 The pseudocode above employs the following macro definitions. 1152 Boundary(I,G) evaluates to TRUE if an administratively scoped boundary 1153 for group G is configured on interface I. 1155 StateRefreshCapable(I) evaluates to TRUE if all neighbors on an 1156 interface use the State Refresh option. 1158 StateRefreshRateLimit(S,G) evaluates to TRUE if the time elapsed since 1159 the last received StateRefresh(S,G) is less than the configured 1160 RefreshLimitInterval. 1162 TTL(SRM) returns the TTL contained in the State Refresh Message, SRM. 1163 This is different from the TTL contained in the IP header. 1165 Threshold(I) returns the minimum TTL that a packet must have before it 1166 can be transmitted on interface I. 1168 srcaddr(SRM) returns the source address contained in the network 1169 protocol (e.g. IPv4) header of the State Refresh Message, SRM. 1171 my_addr(I) returns this node's network (e.g. IPv4) address on interface 1172 I. 1174 4.5.2 State Refresh Message Origination 1176 This section describes the origination of State Refresh messages. These 1177 messages are generated periodically by the PIM-DM router that is 1178 directly connected to a source. One Origination(S,G) state machine 1179 exists per (S,G) entry in a PIM-DM router. 1181 The Origination(S,G) state machine has the following states: 1183 NotOriginator(NO) 1184 This is the starting state of the Origination(S,G) state machine. 1185 While in this state a router will not originate State Refresh 1186 messages for the (S,G) pair. 1188 Originator(O) 1189 When in this state the router will periodically originate State 1190 Refresh messages. Only routers which are directly connected to S 1191 may transition to this state. 1193 In addition there are two state-machine-specific timers: 1195 State Refresh Timer (SRT(S,G)) 1196 This timer is controls when State Refresh messages are generated. 1197 The timer is initially set when that Origination(S,G) state machine 1198 transitions to the O state. It is cancelled when the 1199 Origination(S,G) state machine transitions to the NO state. This 1200 timer is normally set to StateRefreshInterval (see 4.8). 1202 Source Active Timer (SAT(S,G)) 1203 This timer is first set when the Origination(S,G) state machine 1204 transitions to the O state and is reset on the receipt of every 1205 data packet from S addressed to group G. When it expires, the 1206 Origination(S,G) state machine transitions to the NO state. This 1207 timer is normally set to SourceLifetime (see 4.8). 1209 +-------------+ Rcv Directly From S +-------------+ 1210 | |----------------------->| | 1211 |NotOriginator| | Originator | 1212 | |<-----------------------| | 1213 +-------------+ SAT Expires OR +-------------+ 1214 S NOT Direct Connect 1216 Figure 3: State Refresh State Machine 1218 In tabular form, the state machine is defined as follows: 1220 +----------------------------------------------------------------------+ 1221 | | Previous State | 1222 | +---------------+-------------------+ 1223 | Event | NotOriginator | Originator | 1224 +----------------------------------+---------------+-------------------+ 1225 | Receive Data from S AND | ->O | ->O Reset | 1226 | S directly connected | Set SRT(S,G) | SAT(S,G) | 1227 | | Set SAT(S,G) | | 1228 +----------------------------------+---------------+-------------------+ 1229 | SRT(S,G) Expires | N/A | ->O Send | 1230 | | | StateRefresh(S,G) | 1231 | | | Reset SRT(S,G) | 1232 +----------------------------------+---------------+-------------------+ 1233 | SAT(S,G) Expires | N/A | ->NO Cancel | 1234 | | | SRT(S,G) | 1235 +----------------------------------+---------------+-------------------+ 1236 | S no longer directly connected | ->NO | ->NO | 1237 | | | Cancel SRT(S,G) | 1238 | | | Cancel SAT(S,G) | 1239 +----------------------------------+---------------+-------------------+ 1240 4.5.2.1. Transitions from the NotOriginator (NO) State 1242 When the Originating(S,G) state machine is in the NotOriginator (NO) 1243 state, the following event may trigger a transition: 1245 Data Packet received from directly connected Source S addressed to 1246 group G 1247 The router MUST transition to an Originator (O) state, set SAT(S,G) 1248 to SourceLifetime, and set SRT(S,G) to StateRefreshInterval. The 1249 router SHOULD record the TTL of the packet for use in State Refresh 1250 messages. 1252 4.5.2.2. Transitions from the Originator (O) State 1254 When the Originating(S,G) state machine is in the Originator (O) state, 1255 the following events may trigger a transition: 1257 Receive Data Packet from S addressed to G 1258 The router remains in the Originator (O) state and MUST reset 1259 SAT(S,G) to SourceLifetime. The router SHOULD increase its recorded 1260 TTL to match the TTL of the packet, if the packet's TTL is larger 1261 than the previously recorded TTL. 1263 SRT(S,G) Expires 1264 The router remains in the Originator (O) state and MUST reset 1265 SRT(S,G) to StateRefreshInterval. The router MUST also generate 1266 State Refresh messages for transmission as described in the State 1267 Refresh Forwarding rules (section 4.5.1) except for the TTL. If the 1268 TTL of data packets from S to G are being recorded, then the TTL of 1269 each State Refresh message is set to the highest recorded TTL. 1270 Otherwise, the TTL is set to the configured State Refresh TTL. Let 1271 I denote the interface over which a State Refresh message is being 1272 sent. If the Prune(S,G) Downstream state machine for I is in the 1273 NoInfo (NI) state, then the Prune-Indicator bit MUST be set to 0 in 1274 the State Refresh message being sent over I. Otherwise the 1275 Prune-Indicator bit MUST be set to 1. 1277 SAT(S,G) Expires 1278 The router MUST cancel the SRT(S,G) timer and transition to the 1279 NotOriginator (NO) state. 1281 S is no longer directly connected 1282 The router MUST transition to the NotOriginator (NO) state and 1283 cancel both the SAT(S,G) and SRT(S,G). 1285 4.6. PIM Assert Messages 1287 4.6.1. Assert Metrics 1289 Assert metrics are defined as: 1291 struct assert_metric { 1292 metric_preference; 1293 route_metric; 1294 ip_address; 1295 }; 1297 When comparing assert_metrics, the metric_preference and route_metric 1298 field are compared in order, where the first lower value wins. If all 1299 fields are equal, the IP address of the router that sourced the Assert 1300 message is used as a tie-breaker, with the highest IP address winning. 1302 An Assert metric for (S,G) to include in (or compare against) an Assert 1303 message sent on interface I should be computed using the following 1304 pseudocode: 1306 assert_metric 1307 my_assert_metric(S,G,I) { 1308 if (CouldAssert(S,G,I) == TRUE) { 1309 return spt_assert_metric(S,G,I) 1310 } else { 1311 return infinite_assert_metric() 1312 } 1313 } 1315 spt_assert_metric(S,I) gives the Assert metric we use if we're sending 1316 an Assert based on active (S,G) forwarding state: 1318 assert_metric 1319 spt_assert_metric(S,I) { 1320 return {0,MRIB.pref(S),MRIB.metric(S),my_addr(I)} 1321 } 1323 MRIB.pref(X) and MRIB.metric(X) are the routing preference and routing 1324 metrics associated with the route to a particular (unicast) destination 1325 X, as determined by the MRIB. my_addr(I) is simply the router's network 1326 (e.g. IP) address that is associated with the local interface I. 1328 infinite_assert_metric() gives the Assert metric we need to send an 1329 Assert but doesn't match (S,G) forwarding state: 1331 assert_metric 1332 infinite_assert_metric() { 1333 return {1,infinity,infinity,0} 1334 } 1335 4.6.2. AssertCancel Messages 1337 An AssertCancel(S,G) message is simply an Assert message for (S,G) with 1338 infinite metric. The Assert winner sends such a message when it changes 1339 its upstream interface to this interface. Other routers will see this 1340 metric, causing those with forwarding state to send their own Asserts 1341 and re-establish an Assert winner. 1343 AssertCancel messages are simply an optimization. The original Assert 1344 timeout mechanism will allow a subnet to eventually become consistent; 1345 the AssertCancel mechanism simply causes faster convergence. No special 1346 processing is required for an AssertCancel message, since it is simply 1347 an Assert message from the current winner. 1349 4.6.3. Assert State Macros 1351 The macro lost_assert(S,G,I), is used in the olist computations of 1352 section 4.1.3, and is defined as follows: 1354 bool lost_assert(S,G,I) { 1355 if ( RPF_interface(S) == I ) { 1356 return FALSE 1357 } else { 1358 return (AssertWinner(S,G,I) != me AND 1359 (AssertWinnerMetric(S,G,I) is better than 1360 spt_assert_metric(S,G,I))) 1361 } 1362 } 1364 AssertWinner(S,G,I) defaults to NULL and AssertWinnerMetric(S,G,I) 1365 defaults to Infinity when in the NoInfo state. 1367 4.6.4. (S,G) Assert Message State Machine 1369 The (S,G) Assert state machine for interface I is shown in Figure 4. 1370 There are three states: 1372 NoInfo (NI) 1373 This router has no (S,G) Assert state on interface I. 1375 I am Assert Winner (W) 1376 This router has won an (S,G) Assert on interface I. It is now 1377 responsible for forwarding traffic from S destined for G via 1378 interface I. 1380 I am Assert Loser (L) 1381 This router has lost an (S,G) Assert on interface I. It must not 1382 forward packets from S destined for G onto interface I. 1384 In addition there is also an Assert Timer (AT(S,G,I)) that is used to 1385 time out Assert state. 1387 +-------------+ +-------------+ 1388 | | Rcv Pref Assert or SR | | 1389 | Winner |----------------------->| Loser | 1390 | | | | 1391 +-------------+ +-------------+ 1392 ^ | ^ | 1393 | | Rcv Pref Assert or| | 1394 | |AT Expires OR State Refresh| | 1395 | |CouldAssert->FALSE | | 1396 | | | | 1397 | | +-------------+ | | 1398 | +-------->| |----------+ | 1399 | | No Info | | 1400 +-------------| |<-------------+ 1401 Rcv Data from dnstrm +-------------+ Rcv Inf Assert from Win OR 1402 OR Rcv Inferior Assert Rcv Inf SR from Winner OR 1403 OR Rcv Inferior SR AT Expires OR 1404 CouldAssert Changes OR 1405 Winner's NLT Expires 1407 Figure 4: Assert State Machine 1409 In tabular form the state machine is defined as follows: 1411 +-------------------------------+--------------------------------------+ 1412 | | Previous State | 1413 | +------------+------------+------------+ 1414 | Event | No Info | Winner | Loser | 1415 +-------------------------------+------------+------------+------------+ 1416 | An (S,G) Data packet received | ->W Send | ->W Send | ->L | 1417 | on downstream interface | Assert(S,G)| Assert(S,G)| | 1418 | | Set | Set | | 1419 | | AT(S,G,I) | AT(S,G,I) | | 1420 +-------------------------------+--------------------------------------+ 1421 | Receive Inferior (Assert OR | N/A | N/A |->NI Cancel | 1422 | State Refresh) from Assert | | | AT(S,G,I) | 1423 | Winner | | | | 1424 +-------------------------------+--------------------------------------+ 1425 | Receive Inferior (Assert OR | ->W Send | ->W Send | ->L | 1426 | State Refresh) from non-Assert| Assert(S,G)| Assert(S,G)| | 1427 | Winner AND CouldAssert==TRUE | Set | Set | | 1428 | | AT(S,G,I) | AT(S,G,I) | | 1429 +-------------------------------+--------------------------------------+ 1430 +-------------------------------+--------------------------------------+ 1431 | | Previous State | 1432 | +------------+------------+------------+ 1433 | Event | No Info | Winner | Loser | 1434 +-------------------------------+------------+------------+------------+ 1435 | Receive Preferred Assert OR | ->L Send | ->L Send | ->L Set | 1436 | State Refresh | Prune(S,G) | Prune(S,G) | AT(S,G,I) | 1437 | | Set | Set | | 1438 | | AT(S,G,I) | AT(S,G,I) | | 1439 +-------------------------------+--------------------------------------+ 1440 | Send State Refresh | ->NI | ->W Reset | N/A | 1441 | | | AT(S,G,I) | | 1442 +-------------------------------+--------------------------------------+ 1443 | AT(S,G) Expires | N/A | ->NI | ->NI | 1444 +-------------------------------+--------------------------------------+ 1445 | CouldAssert -> FALSE | ->NI |->NI Cancel |->NI Cancel | 1446 | | | AT(S,G,I) | AT(S,G,I) | 1447 +-------------------------------+--------------------------------------+ 1448 | CouldAssert -> TRUE | ->NI | N/A |->NI Cancel | 1449 | | | | AT(S,G,I) | 1450 +-------------------------------+--------------------------------------+ 1451 | Winner's NLT(N,I) Expires | N/A | N/A |->NI Cancel | 1452 | | | | AT(S,G,I) | 1453 +-------------------------------+--------------------------------------+ 1454 | Receive Prune(S,G), Join(S,G) | ->NI | ->W | ->L Send | 1455 | or Graft(S,G) | | | Assert(S,G)| 1456 +-------------------------------+--------------------------------------+ 1458 Terminology: 1459 A "preferred assert" is one with a better metric than the current 1460 winner. An "inferior assert" is one with a worse metric than 1461 my_assert_metric(S,G,I). 1463 The state machine uses the following macro: 1465 CouldAssert(S,G,I) = (RPF_interface(S) != I) 1467 4.6.4.1. Transitions from NoInfo State 1469 When in NoInfo state, the following events may trigger transitions: 1471 An (S,G) data packet arrives on downstream interface I 1472 An (S,G) data packet arrived on a downstream interface. It is 1473 optimistically assumed that this router will be the Assert winner 1474 for this (S,G). The Assert state machine MUST transition to the "I 1475 am Assert Winner" state, send an Assert(S,G) to interface I, store 1476 its own address and metric as the Assert Winner and set the 1477 Assert_Timer (AT(S,G,I) to Assert_Time, thereby initiating the 1478 Assert negotiation for (S,G). 1480 Receive Inferior (Assert OR State Refresh) AND 1481 CouldAssert(S,G,I)==TRUE 1482 An Assert or State Refresh is received for (S,G) that is inferior 1483 to our own assert metric on interface I. The Assert state machine 1484 MUST transition to the "I am Assert Winner" state, send an 1485 Assert(S,G) to interface I, store its own address and metric as the 1486 Assert Winner and set the Assert Timer (AT(S,G,I)) to Assert_Time. 1488 Receive Preferred Assert or State Refresh 1489 The received Assert or State Refresh has a better metric than this 1490 router's and therefore the Assert state machine MUST transition to 1491 the "I am Assert Loser" state and store the Assert Winner's address 1492 and metric. If the metric was received in an Assert, the router MUST 1493 set the Assert Timer (AT(S,G,I)) to Assert_Time. If the metric was 1494 received in a State Refresh, the router MUST set the Assert Timer 1495 (AT(S,G,I)) to three times the received State Refresh Interval. If 1496 CouldAssert(S,G,I) == TRUE, the router MUST also multicast a 1497 Prune(S,G) to the Assert winner with a Prune Hold Time equal to the 1498 Assert Timer and evaluate any changes in its Upstream(S,G) state 1499 machine. 1501 4.6.4.2. Transitions from Winner State 1503 When in "I am Assert Winner" state, the following events trigger 1504 transitions: 1506 An (S,G) data packet arrives on downstream interface I 1507 An (S,G) data packet arrived on a downstream interface. The Assert 1508 state machine remains in the "I am Assert Winner" state. The router 1509 MUST send an Assert(S,G) to interface I and set the Assert Timer 1510 (AT(S,G,I) to Assert_Time. 1512 Receive Inferior Assert or State Refresh 1513 An (S,G) Assert is received containing a metric for S that is worse 1514 metric than this router's metric for S. Whoever sent the Assert is 1515 in error. The router MUST send an Assert(S,G) to interface I and 1516 reset the Assert Timer (AT(S,G,I)) to Assert_Time. 1518 Receive Preferred Assert or State Refresh 1519 An (S,G) Assert or State Refresh is received that has a better 1520 metric than this router's metric for S on interface I. The Assert 1521 state machine MUST transition to "I am Assert Loser" state and 1522 store the new Assert Winner's address and metric. If the metric was 1523 received in an Assert, the router MUST set the Assert Timer 1524 (AT(S,G,I)) to Assert_Time. If the metric was received in a State 1525 Refresh, the router MUST set the Assert Timer (AT(S,G,I)) to three 1526 times the State Refresh Interval. The router MUST also multicast a 1527 Prune(S,G) to the Assert winner with a Prune Hold Time equal to the 1528 Assert Timer and evaluate any changes in its Upstream(S,G) state 1529 machine. 1531 Send State Refresh 1532 The router is sending a State Refresh(S,G) message on interface I. 1533 The router MUST set the Assert Timer (AT(S,G,I)) to three times the 1534 State Refresh Interval contained in the State Refresh(S,G) message. 1536 AT(S,G,I) Expires 1537 The (S,G) Assert Timer (AT(S,G,I)) expires. The Assert state machine 1538 MUST transition to the NoInfo (NI) state. 1540 CouldAssert(S,G,I) -> FALSE 1541 This router's RPF interface changed so as to make CouldAssert(S,G,I) 1542 become false. This router can no longer perform the actions of the 1543 Assert winner, and so the Assert state machine MUST transition to 1544 NoInfo (NI) state, send an AssertCancel(S,G) to interface I, cancel 1545 the Assert Timer (AT(S,G,I)) and remove itself as the Assert Winner. 1547 4.6.4.3. Transitions from Loser State 1549 When in "I am Assert Loser" state, the following transitions can occur: 1551 Receive Inferior Assert or State Refresh from Current Winner 1552 An Assert or State Refresh is received from the current Assert 1553 winner that is worse than this router's metric for S (typically the 1554 winner's metric became worse). The Assert state machine MUST 1555 transition to NoInfo (NI) state and cancel AT(S,G,I). The router 1556 MUST delete the previous Assert Winner's address and metric and 1557 evaluate any possible transitions to its Upstream(S,G) state 1558 machine. Usually this router will eventually re-assert and win when 1559 data packets from S have started flowing again. 1561 Receive Preferred Assert or State Refresh 1562 An Assert or State Refresh is received that has a metric better than 1563 or equal to that of the current Assert winner. The Assert state 1564 machine remains in Loser (L) state. If the metric was received in 1565 an Assert, the router MUST set the Assert Timer (AT(S,G,I)) to 1566 Assert_Time. If the metric was received in a State Refresh, the 1567 router MUST set the Assert Timer (AT(S,G,I)) to three times the 1568 received State Refresh Interval. If the metric is better than the 1569 current Assert Winner, the router MUST store the address and metric 1570 of the new Assert Winner and if CouldAssert(S,G,I) == TRUE, the 1571 router MUST multicast a Prune(S,G) to the new Assert winner. 1573 AT(S,G,I) Expires 1574 The (S,G) Assert Timer (AT(S,G,I)) expires. The Assert state 1575 machine MUST transition to NoInfo (NI) state. The router MUST 1576 delete the Assert Winner's address and metric. If CouldAssert == 1577 TRUE, the router MUST evaluate any possible transitions to its 1578 Upstream(S,G) state machine. 1580 CouldAssert -> FALSE 1581 CouldAssert has become FALSE because interface I has become the RPF 1582 interface for S. The Assert state machine MUST transition to NoInfo 1583 (NI) state, cancel AT(S,G,I) and delete information concerning the 1584 Assert Winner on I. 1586 CouldAssert -> TRUE 1587 CouldAssert has become TRUE because interface I used to be the RPF 1588 interface for S, and now it is not. The Assert state machine MUST 1589 transition to NoInfo (NI) state, cancel AT(S,G,I) and delete 1590 information concerning the Assert Winner on I. 1592 Current Assert Winner's NeighborLiveness Timer Expires 1593 The current Assert winner's NeighborLiveness Timer (NLT(N,I)) has 1594 expired. The Assert state machine MUST transition to the NoInfo 1595 (NI) state, delete the Assert Winner's address and metric, and 1596 evaluate any possible transitions to its Upstream(S,G) state 1597 machine. 1599 Receive Prune(S,G), Join(S,G) or Graft(S,G) 1600 A Prune(S,G), Join(S,G) or Graft(S,G) message was received on 1601 interface I with its upstream neighbor address set to the router's 1602 address on I. The router MUST send an Assert(S,G) on the receiving 1603 interface I to initiate an Assert negotiation. The Assert state 1604 machine remains in the Assert Loser(L) state. If a Graft(S,G) was 1605 received, the router MUST respond with a GraftAck(S,G). 1607 4.6.5. Rationale for Assert Rules 1609 The following is a summary of the rules for generating and processing 1610 Assert messages. It is not intended to be definitive (the state 1611 machines and pseudocode provide the definitive behavior). Instead it 1612 provides some rationale for the behavior. 1614 1. The Assert winner for (S,G) must act as the local forwarder for (S,G) 1615 on behalf of all downstream members. 1616 2. PIM messages are directed towards to the RPF' neighbor and not to the 1617 regular RPF neighbor. 1618 3. An Assert loser that receives a Prune(S,G), Join(S,G) or Graft(S,G) 1619 directed to it initiates a new Assert negotiation so the downstream 1620 router can correct its RPF'(S). 1621 4. An Assert winner for (S,G) sends a cancelling assert when it is about 1622 to stop forwarding on an (S,G) entry. Example: if a router is being 1623 taken down, then a canceling assert is sent. 1625 4.7. PIM Packet Formats 1627 All PIM-DM packets use the same format as PIM-SM packets. In the event 1628 of a discrepancy, PIM-SM [4] should be considered the definitive 1629 specification. All PIM control messages have IP protocol number 103. 1630 All PIM-DM messages MUST be sent with a TTL of 1. All PIM-DM messages 1631 except Graft and Graft Ack messages MUST be sent to the ALL-PIM-ROUTERS 1632 group. Graft messages SHOULD be unicast to the RPF'(S). Graft Ack 1633 messages MUST be unicast to the sender of the Graft. 1635 The IPv4 ALL-PIM-ROUTERS group is 224.0.0.13. The IPv6 ALL-PIM-ROUTERS 1636 group is 'ff02::d'. 1638 4.7.1. PIM Header 1640 All PIM control messages have the following header: 1642 0 1 2 3 1643 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 1644 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1645 |PIM Ver| Type | Reserved | Checksum | 1646 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1648 PIM Ver 1649 PIM version number is 2. 1651 Type 1652 Types for specific PIM messages. Available types are: 1653 0 = Hello 1654 1 = Register (PIM-SM only) 1655 2 = Register Stop (PIM-SM only) 1656 3 = Join/Prune 1657 4 = Bootstrap (PIM-SM only) 1658 5 = Assert 1659 6 = Graft 1660 7 = Graft Ack 1661 8 = Candidate RP Advertisement (PIM-SM only) 1662 9 = State Refresh 1664 Reserved 1665 Set to zero on transmission. Ignored upon receipt. 1667 Checksum 1668 The checksum is standard IP checksum, i.e. the 16 bit one's complement 1669 of the one's complement sum of the entire PIM message. For computing 1670 checksum, the checksum field is zeroed. 1672 For IPv6, the checksum also includes the IPv6 "pseudo-header", as 1673 specified in RFC 2460, section 8.1 [13]. 1675 4.7.2. Encoded Unicast Address 1677 An Encoded Unicast Address has the following format: 1679 0 1 2 3 1680 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 1681 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1682 | Addr Family | Encoding Type | Unicast Address 1683 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+... 1685 Addr Family 1686 The PIM Address Family of the 'Unicast Address' field of this address. 1687 Values of 0-127 are as assigned by the IANA for Internet Address 1688 Families in [9]. Values 128-250 are reserved to be assigned by the 1689 IANA for PIM specific Address Families. Values 251-255 are designated 1690 for private use. As there is no assignment authority for this space, 1691 collisions should be expected. 1693 Encoding Type 1694 The type of encoding used with a specific Address Family. The value 1695 '0' is reserved for this field, and represents the native encoding of 1696 the Address Family 1698 Unicast Address 1699 The unicast address as represented by the given Address Family and 1700 Encoding Type. 1702 4.7.3. Encoded Group Address 1704 An Encoded Group address has the following format: 1706 0 1 2 3 1707 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 1708 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1709 | Addr Family | Encoding Type |B| Reserved |Z| Mask Len | 1710 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1711 | Group Multicast Address 1712 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+... 1714 Addr Family 1715 As described above. 1717 Encoding Type 1718 As described above. 1720 B 1721 Indicates the group range should use Bidirectional PIM [16]. 1722 Transmitted as zero, ignored upon receipt. 1724 Reserved 1725 Transmitted as zero. Ignored upon receipt. 1727 Z 1728 Indicates the group range is an admin scope zone. This is used in the 1729 Bootstrap Router Mechanism [18] only. For all other purposes, this bit 1730 is set to zero and ignored on receipt. 1732 Mask Len 1733 The mask length field is 8 bits. The value is the number of 1734 contiguous on bits left justified used as a mask, which combined with 1735 the address, describes a range of addresses. It is less than or equal 1736 to the address length in bits for the given Address Family and 1737 Encoding Type. If the message is sent for a single address then the 1738 mask length MUST equal the address length. PIM-DM routers MUST only 1739 send for a single address. 1741 Group Multicast Address 1742 The address of the multicast group. 1744 4.7.4. Encoded Source Address 1746 An Encoded Source address has the following format: 1748 0 1 2 3 1749 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 1750 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1751 | Addr Family | Encoding Type | Rsrvd |S|W|R| Mask Len | 1752 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1753 | Source Address 1754 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+... 1756 Addr Family 1757 As described above. 1759 Encoding Type 1760 As described above. 1762 Rsrvd 1763 Reserved. Transmitted as zero. Ignored upon receipt. 1765 S 1766 The Sparse Bit. Set to 0 for PIM-DM. Ignored upon receipt. 1768 W 1769 The Wild Card Bit. Set to 0 for PIM-DM. Ignored upon receipt. 1771 R 1772 The Rendezvous Point Tree bit. Set to 0 for PIM-DM. Ignored upon 1773 receipt. 1775 Mask Len 1776 As described above. PIM-DM routers MUST only send for a single 1777 source address. 1779 Source Address 1780 The source address. 1782 4.7.5. Hello Message Format 1784 The PIM Hello message, as defined by PIM-SM [4], has the following 1785 format: 1787 0 1 2 3 1788 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 1789 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1790 |PIM Ver| Type | Reserved | Checksum | 1791 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1792 | Option Type | Option Length | 1793 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1794 | Option Value | 1795 | ... | 1796 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1797 | . | 1798 | . | 1799 | . | 1800 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1801 | Option Type | Option Length | 1802 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1803 | Option Value | 1804 | ... | 1805 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1807 PIM Ver, Type, Reserved, Checksum 1808 Described above. 1810 Option Type 1811 The type of option given in the Option Value field. Available types 1812 are: 1813 0 Reserved 1814 1 Hello Hold Time 1815 2 LAN Prune Delay 1816 3-16 Reserved 1817 17 To be assigned by IANA 1818 18 Deprecated and SHOULD NOT be used 1819 19 DR Priority (PIM-SM Only) 1820 20 Generation ID 1821 21 State Refresh Capable 1822 22 Bidir Capable 1823 23-65000 To be assigned by IANA 1824 65001-65535 Reserved for Private Use [9] 1825 Unknown options SHOULD be ignored. 1827 4.7.5.1. Hello Hold Time Option 1829 0 1 2 3 1830 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 1831 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1832 | Type = 1 | Length = 2 | 1833 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1834 | Hold Time | 1835 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1837 Hold Time is the number of seconds a receiver MUST keep the neighbor 1838 reachable. If the Hold Time is set to '0xffff', the receiver of this 1839 message never times out the neighbor. This may be used with dial-on- 1840 demand links, to avoid keeping the link up with periodic Hello messages. 1841 Furthermore, if the Holdtime is set to '0', the information is timed out 1842 immediately. The Hello Hold Time option MUST be used by PIM-DM routers. 1844 4.7.5.2. LAN Prune Delay Option 1846 0 1 2 3 1847 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 1848 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1849 | Type = 2 | Length = 4 | 1850 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1851 |T| LAN Prune Delay | Override Interval | 1852 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1854 The LAN_Prune_Delay option is used to tune the prune propagation delay 1855 on multi-access LANs. The T bit is used by PIM-SM and SHOULD be set to 0 1856 by PIM-DM routers and ignored upon receipt. The LAN Delay and Override 1857 Interval fields are time intervals in units of milliseconds and are used 1858 to tune the value of the J/P Override Interval and its derived timer 1859 values. Section 4.3.5 describes how these values affect the behavior of 1860 a router. The LAN Prune Delay SHOULD be used by PIM-DM routers. 1862 4.7.5.3. Generation ID Option 1864 0 1 2 3 1865 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 1866 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1867 | Type = 20 | Length = 4 | 1868 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1869 | Generation ID | 1870 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1872 Generation ID is a random value for the interface on which the Hello 1873 message is sent. The Generation ID is regenerated whenever PIM 1874 forwarding is started or restarted on the interface. The Generation ID 1875 option MAY be used by PIM-DM routers. 1877 4.7.5.4. State Refresh Capable Option 1879 0 1 2 3 1880 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 1881 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1882 | Type = 21 | Length = 4 | 1883 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1884 | Version = 1 | Interval | Reserved | 1885 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1887 The Interval field is the router's configured State Refresh Interval in 1888 seconds. The Reserved field is set to zero and ignored upon reception. 1889 The State Refresh Capable option MUST be used by State Refresh capable 1890 PIM-DM routers. 1892 4.7.6. Join/Prune Message Format 1894 PIM Join/Prune messages, as defined in PIM-SM [4], have the following 1895 format: 1897 0 1 2 3 1898 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 1899 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1900 |PIM Ver| Type | Reserved | Checksum | 1901 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1902 | Upstream Neighbor Address (Encoded Unicast Format) | 1903 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1904 | Reserved | Num Groups | Hold Time | 1905 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1906 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1907 | Multicast Group Address 1 (Encoded Group Format) | 1908 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1909 | Number of Joined Sources | Number of Pruned Sources | 1910 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1911 | Joined Source Address 1 (Encoded Source Format) | 1912 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1913 | . | 1914 | . | 1915 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1916 | Joined Source Address n (Encoded Source Format) | 1917 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1918 | Pruned Source Address 1 (Encoded Source Format) | 1919 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1920 | . | 1921 | . | 1922 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1923 | Pruned Source Address n (Encoded Source Format) | 1924 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1925 | . | 1926 | . | 1927 | . | 1928 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1929 | Multicast Group Address m (Encoded Group Format) | 1930 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1931 | Number of Joined Sources | Number of Pruned Sources | 1932 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1933 | Joined Source Address 1 (Encoded Source Format) | 1934 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1935 | . | 1936 | . | 1937 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1938 | Joined Source Address n (Encoded Source Format) | 1939 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1940 | Pruned Source Address 1 (Encoded Source Format) | 1941 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1942 | . | 1943 | . | 1944 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1945 | Pruned Source Address n (Encoded Source Format) | 1946 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1948 PIM Ver, Type, Reserved, Checksum 1949 Described above. 1951 Upstream Neighbor Address 1952 The address of the upstream neighbor. The format for this address is 1953 given in the Encoded Unicast address in section 4.7.2. PIM-DM routers 1954 MUST set this field to the RPF next hop. 1956 Reserved 1957 Transmitted as zero. Ignored upon receipt. 1959 Hold Time 1960 The number of seconds a receiving PIM-DM router MUST keep a Prune 1961 state alive, unless removed by a Join or Graft message. If the Hold 1962 Time is '0xffff', the receiver MUST NOT remove the Prune state unless 1963 a corresponding Join or Graft message is received. The Hold Time is 1964 ignored in Join messages. 1966 Number of Groups 1967 Number of multicast group sets contained in the message. 1969 Multicast Group Address 1970 The multicast group address in the Encoded Multicast address format 1971 given in section 4.7.3. 1973 Number of Joined Sources 1974 Number of Join source addresses listed for a given group. 1976 Number of Pruned Sources 1977 Number of Prune source addresses listed for a given group. 1979 Join Source Address 1..n 1980 This list contains the sources from which the sending router wishes to 1981 continue to receive multicast messages for the given group on this 1982 interface. The addresses use the Encoded Source address format given 1983 in section 4.7.4. 1985 Prune Source Address 1..n 1986 This list contains the sources from which the sending router does not 1987 wish to receive multicast messages for the given group on this 1988 interface. The addresses use the Encoded Source address format given 1989 in section 4.7.4. 1991 4.7.7. Assert Message Format 1993 PIM Assert Messages, as defined in PIM-SM [4], have the following 1994 format: 1996 0 1 2 3 1997 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 1998 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1999 |PIM Ver| Type | Reserved | Checksum | 2000 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2001 | Multicast Group Address (Encoded Group Format) | 2002 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2003 | Source Address (Encoded Unicast Format) | 2004 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2005 |R| Metric Preference | 2006 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2007 | Metric | 2008 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2009 PIM Ver, Type, Reserved, Checksum 2010 Described above. 2012 Multicast Group Address 2013 The multicast group address in the Encoded Multicast address format 2014 given in section 4.7.3. 2016 Source Address 2017 The source address in the Encoded Unicast address format given in 2018 section 4.7.2. 2020 R 2021 The Rendezvous Point Tree bit. Set to 0 for PIM-DM. Ignored upon 2022 receipt. 2024 Metric Preference 2025 The preference value assigned to the unicast routing protocol that 2026 provided the route to the source. 2028 Metric 2029 The cost metric of the unicast route to the source. The metric is in 2030 units applicable to the unicast routing protocol used. 2032 4.7.8. Graft Message Format 2034 PIM Graft messages use the same format as Join/Prune messages except the 2035 Type field is set to 6. The source address MUST be in the Join section 2036 of the message. The Hold Time field SHOULD be zero and SHOULD be 2037 ignored when a Graft is received. 2039 4.7.9. Graft Ack Message Format 2041 PIM Graft Ack messages are identical in format to the received Graft 2042 message except the Type field is set to 7. The Upstream Neighbor 2043 Address field SHOULD be set to the sender of the Graft message and 2044 SHOULD be ignored upon receipt. 2046 4.7.10. State Refresh Message Format 2048 PIM State Refresh Messages have the following format: 2050 0 1 2 3 2051 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 2052 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2053 |PIM Ver| Type | Reserved | Checksum | 2054 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2055 | Multicast Group Address (Encoded Group Format) | 2056 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2057 | Source Address (Encoded Unicast Format) | 2058 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2059 | Originator Address (Encoded Unicast Format) | 2060 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2061 |R| Metric Preference | 2062 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2063 | Metric | 2064 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2065 | Masklen | TTL |P|N|O|Reserved | Interval | 2066 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2068 PIM Ver, Type, Reserved, Checksum 2069 Described above. 2071 Multicast Group Address 2072 The multicast group address in the Encoded Multicast address format 2073 given in section 4.7.3. 2075 Source Address 2076 The address of the data source in the Encoded Unicast address format 2077 given in section 4.7.2. 2079 Originator Address 2080 The address of the first hop router in the Encoded Unicast address 2081 format given in section 4.7.2. 2083 R 2084 The Rendezvous Point Tree bit. Set to 0 for PIM-DM. Ignored upon 2085 receipt. 2087 Metric Preference 2088 The preference value assigned to the unicast routing protocol that 2089 provided the route to the source. 2091 Metric 2092 The cost metric of the unicast route to the source. The metric is in 2093 units applicable to the unicast routing protocol used. 2095 Masklen 2096 The length of the address mask of the unicast route to the source. 2098 TTL 2099 Time To Live of the State Refresh message. Decremented each time the 2100 message is forwarded. Note that this is different from the IP Header 2101 TTL, which is always set to 1. 2103 P 2104 Prune indicator flag. This MUST be set to 1 if the State Refresh is 2105 to be sent on a Pruned interface. Otherwise, it MUST be set to 0. 2107 N 2108 Prune Now flag. This SHOULD be set to 1 by the State Refresh 2109 originator on every third State Refresh message and SHOULD be ignored 2110 upon receipt. This is for compatibility with earlier versions of 2111 state refresh. 2113 O 2114 Assert Override flag. This SHOULD be set to 1 by upstream routers on 2115 a LAN if the Assert Timer (AT(S,G)) is not running and SHOULD be 2116 ignored upon receipt. This is for compatibility with earlier versions 2117 of state refresh. 2119 Reserved 2120 Set to zero and ignored upon receipt. 2122 Interval 2123 Set by the originating router to the interval (in seconds) between 2124 consecutive State Refresh messages for this (S,G) pair. 2126 4.8. PIM-DM Timers 2128 PIM-DM maintains the following timers. All timers are countdown timers 2129 - they are set to a value and count down to zero, at which point they 2130 typically trigger an action. Of course they can just as easily be 2131 implemented as count-up timers, where the absolute expiry time is stored 2132 and compared against a real-time clock, but the language in this 2133 specification assumes that they count downwards towards zero. 2135 Global Timers 2136 Hello Timer: HT 2138 Per interface (I): 2139 Per neighbor (N): 2140 Neighbor Liveness Timer: NLT(N,I) 2142 Per (S,G) Pair: 2143 (S,G) Assert Timer: AT(S,G,I) 2144 (S,G) Prune Timer: PT(S,G,I) 2145 (S,G) PrunePending Timer: PPT(S,G,I) 2147 Per (S,G) Pair: 2148 (S,G) Graft Retry Timer: GRT(S,G) 2149 (S,G) Upstream Override Timer: OT(S,G) 2150 (S,G) Prune Limit Timer: PLT(S,G) 2151 (S,G) Source Active Timer: SAT(S,G) 2152 (S,G) State Refresh Timer: SRT(S,G) 2154 When timer values are started or restarted, they are set to default 2155 values. The following tables summarize those default values. 2157 Timer Name: Hello Timer (HT) 2158 +----------------------+--------+--------------------------------------+ 2159 | Value Name | Value | Explanation | 2160 +----------------------+--------+--------------------------------------+ 2161 |Hello_Period | 30 sec | Periodic interval for hello messages | 2162 +----------------------+--------+--------------------------------------+ 2163 |Triggered_Hello_Delay | 5 sec | Random interval for initial Hello | 2164 | | | message on bootup or triggered Hello | 2165 | | | message to a rebooting neighbor | 2166 +----------------------+--------+--------------------------------------+ 2168 Hello message are sent on every active interface once every Hello_Period 2169 seconds. At system power-up, the timer is initialized to 2170 rand(0,Triggered_Hello_Delay) to prevent synchronization. When a new or 2171 rebooting neighbor is detected, a responding Hello is sent within 2172 rand(0,Triggered_Hello_Delay). 2174 Timer Name: Neighbor Liveness Timer (NLT(N,I)) 2175 +-------------------+-----------------+--------------------------------+ 2176 | Value Name | Value | Explanation | 2177 +-------------------+-----------------+--------------------------------+ 2178 | Hello Holdtime | From message | Hold Time from Hello Message | 2179 +-------------------+-----------------+--------------------------------+ 2181 Timer Name: PrunePending Timer (PPT(S,G,I)) 2182 +-----------------------+---------------+------------------------------+ 2183 | Value Name | Value | Explanation | 2184 +-----------------------+---------------+------------------------------+ 2185 | J/P_Override_Interval | OI(I) + PD(I) | Short time after a Prune to | 2186 | | | allow other routers on the | 2187 | | | LAN to send a Join | 2188 +-----------------------+---------------+------------------------------+ 2190 The J/P_Override_Interval is the sum of the interface's 2191 Override_Interval (OI(I)) and Propagation_Delay (PD(I)). If all routers 2192 on a LAN are using the LAN Prune Delay option, both parameters MUST be 2193 set to the largest value on the LAN. Otherwise, the Override_Interval 2194 (OI(I)) MUST be set to 2.5 seconds and the Propagation_Delay (PD(I)) 2195 MUST be set to 0.5 seconds. 2197 Timer Name: Prune Timer (PT(S,G,I)) 2198 +----------------+----------------+------------------------------------+ 2199 | Value Name | Value | Explanation | 2200 +----------------+----------------+------------------------------------+ 2201 | Prune Holdtime | From message | Hold Time read from Prune Message | 2202 +----------------+----------------+------------------------------------+ 2204 Timer Name: Assert Timer (AT(S,G,I)) 2205 +--------------------------+---------+---------------------------------+ 2206 | Value Name | Value | Explanation | 2207 +--------------------------+---------+---------------------------------+ 2208 | Assert Time | 180 sec | Period after last assert before | 2209 | | | assert state is timed out | 2210 +--------------------------+---------+---------------------------------+ 2212 Note that for historical reasons, the Assert message lacks a Holdtime 2213 field. Thus changing the Assert Time from the default value is not 2214 recommended. If all members of a LAN are state refresh enabled, the 2215 Assert Time will be three times the received RefreshInterval(S,G). 2217 Timer Name: Graft Retry Timer (GRT(S,G)) 2218 +--------------------+-------+-----------------------------------------+ 2219 | Value Name | Value | Explanation | 2220 +--------------------+-------+-----------------------------------------+ 2221 | Graft_Retry_Period | 3 sec | In the absence of receipt of a GraftAck | 2222 | | | message, the time before retransmission | 2223 | | | of a Graft message | 2224 +--------------------+-------+-----------------------------------------+ 2226 Timer Name: Upstream Override Timer (OT(S,G)) 2227 +------------+----------------+----------------------------------------+ 2228 | Value Name | Value | Explanation | 2229 +------------+----------------+----------------------------------------| 2230 | t_override | rand(0, OI(I)) | Randomized delay to prevent response | 2231 | | | implosion when sending a join message | 2232 | | | to override someone else's prune | 2233 +------------+----------------+----------------------------------------+ 2235 t_override is a random value between 0 and the interface's 2236 Override_Interval (OI(I)). If all routers on a LAN are using the LAN 2237 Prune Delay option, the Override_Interval (OI(I)) MUST be set to the 2238 largest value on the LAN. Otherwise, the Override_Interval (OI(I)) MUST 2239 be set to 2.5 seconds. 2241 Timer Name: Prune Limit Timer (PLT(S,G)) 2242 +------------+--------------------+------------------------------------+ 2243 | Value Name | Value | Explanation | 2244 +------------+--------------------+------------------------------------| 2245 | t_limit | Equal to the Prune | Used to prevent Prune storms on a | 2246 | | Holdtime sent | LAN | 2247 +------------+--------------------+------------------------------------+ 2248 Timer Name: Source Active Timer (SAT(S,G)) 2249 +----------------+-------------------+---------------------------------+ 2250 | Value Name | Value | Explanation | 2251 +----------------+-------------------+---------------------------------+ 2252 | SourceLifetime | Default: 210 secs | Period of time after receiving | 2253 | | | a multicast message a directly | 2254 | | | attached router will continue | 2255 | | | to send State Refresh messages | 2256 +----------------+-------------------+---------------------------------+ 2258 Timer Name: State Refresh Timer (SRT(S,G)) 2259 +-----------------+------------------+---------------------------------+ 2260 | Value Name | Value | Explanation | 2261 +-----------------+------------------+---------------------------------+ 2262 | RefreshInterval | Default: 60 secs | Interval between successive | 2263 | | | state refresh messages | 2264 +-----------------+------------------+---------------------------------+ 2266 5. Protocol Interaction Considerations 2268 PIM-DM is designed to be independent of underlying unicast routing 2269 protocols and will interact only to the extent needed to perform RPF 2270 checks. It is generally assumed that multicast area and autonomous 2271 system boundaries will correspond to the same boundaries for unicast 2272 routing, though a deployment which does not follow this assumption is 2273 not precluded by this specification. 2275 In general, PIM-DM interactions with other multicast routing protocols 2276 should be in compliance with RFC 2715 [7]. Other specific 2277 interactions are noted below. 2279 5.1. PIM-SM Interactions 2281 PIM-DM is not intended to interact directly with PIM-SM, even though 2282 they share a common packet format. It is particularly important to note 2283 that a router cannot differentiate between a PIM-DM neighbor and a 2284 PIM-SM neighbor based on Hello messages. 2286 In the event that a PIM-DM router becomes a neighbor of a PIM-SM router 2287 they will effectively form a simplex link with the PIM-DM router sending 2288 all multicast messages to the PIM-SM router while the PIM-SM router 2289 sends no multicast messages to the PIM-DM router. 2291 The common packet format permits a hybrid PIM-SM/DM implementation that 2292 would use PIM-SM when a rendezvous point is known and PIM-DM when one is 2293 not. Such an implementation is outside the scope of this document. 2295 5.2. IGMP Interactions 2297 PIM-DM will forward received multicast data packets to neighboring host 2298 group members in all cases except when the PIM-DM router is in an Assert 2299 Loser state on that interface. Note that a PIM Prune message is not 2300 permitted to prevent the delivery of messages to a network with group 2301 members. 2303 A PIM-DM Router MAY use the DR Priority option described in PIM-SM [13] 2304 to elect an IGMP v1 querier. 2306 5.3. Source Specific Multicast (SSM) Interactions 2308 PIM-DM makes no special considerations for SSM [14]. All Prunes and 2309 Grafts within the protocol are for a specific source, so no additional 2310 checks need be made. 2312 5.4. Multicast Group Scope Boundary Interactions 2314 While multicast group scope boundaries are generally identical to 2315 routing area boundaries, it is conceivable that a routing area might be 2316 partitioned for a particular multicast group. PIM-DM routers MUST NOT 2317 send any messages concerning a particular group across that group's 2318 scope boundary. 2320 6. IANA Considerations 2322 6.1. PIM Address Family 2324 The PIM Address Family field was chosen to be 8 bits as a tradeoff 2325 between packet format and use of the IANA assigned numbers. When the 2326 PIM packet format was designed, only 15 values were assigned for Address 2327 Families and large numbers of new Address Families were not envisioned, 2328 8 bits seemed large enough. However, the IANA assigns Address Families 2329 in a 16 bit value. Therefore, the PIM Address Family is allocated as 2330 follows: 2332 Values 0 through 127 are designated to have the same meaning as IANA 2333 assigned Address Family Numbers [9]. 2335 Values 128 through 250 are designated to be assigned by the IANA based 2336 upon IESG approval as defined in [8]. 2338 Values 251 through 255 are designated for Private Use, as defined in 2339 [8]. 2341 6.2. PIM Hello Options 2343 Values 17 through 65000 are to be assigned by the IANA. Since the space 2344 is large, they may be assigned as First Come First Served as defined in 2345 [8]. Such assignments are valid for one year, and may be renewed. 2346 Permanent assignments require a specification as defined in [8]. 2348 7. Security Considerations 2350 The IPsec authentication header [10] MAY be used to provide data 2351 integrity protection and groupwise data origin authentication of PIM 2352 protocol messages. Authentication of PIM messages can protect against 2353 unwanted behaviors caused by unauthorized or altered PIM messages. In 2354 any case, a PIM router SHOULD NOT accept and process PIM messages from 2355 neighbors unless a valid Hello message has been received from that 2356 neighbor. 2358 We should note that PIM-DM has no rendezvous point, and therefore no 2359 single point of failure that may be vulnerable. It is further worth 2360 noting that because PIM-DM uses unicast routes provided by an unknown 2361 routing protocol, it may suffer collateral effects if the unicast 2362 routing protocol is attacked. 2364 7.1. Attacks Based on Forged Messages 2366 The extent of possible damage depends on the type of counterfeit 2367 messages accepted. We next consider the impact of possible forgeries. A 2368 forged PIM-DM message is link local, and can only reach a LAN if it was 2369 sent by a local host or if it was allowed onto the LAN by a compromised 2370 or non-compliant router. 2372 1. A forged a Hello message can cause multicast traffic to be delivered 2373 to links where there are no legitimate requestors, potentially 2374 wasting bandwidth on that link. On a multi-access LAN, the effects 2375 are limited without the capability to forge a Join message since 2376 other routers will Prune the link if the traffic is not desired. 2378 2. A forged Join/Prune message can cause multicast traffic to be 2379 delivered to links where there are no legitimate requestors, 2380 potentially wasting bandwidth on that link. A forged Prune message 2381 on a multi-access LAN is generally not a significant attack in PIM, 2382 because any legitimately joined router on the LAN would override the 2383 Prune with a Join before the upstream router stops forwarding data 2384 to the LAN. 2386 3. A forged Graft message can cause multicast traffic to be delivered to 2387 links where there are no legitimate requestors, potentially wasting 2388 bandwidth on that link. In principle, Graft messages could be sent 2389 multiple hops since they are unicast to the upstream router. This 2390 should not be a problem since the remote forger should have no way 2391 to get a Hello message to the target of the attack. Without a valid 2392 Hello message, the receiving router SHOULD NOT accept the Graft. 2394 4. A forged GraftAck message has no impact since it will be ignored 2395 unless the router has recently sent a Graft to its upstream router. 2397 5. By forging an Assert message on a multi-access LAN, an attacker could 2398 cause the legitimate forwarder to stop forwarding traffic to the LAN. 2399 Such a forgery would prevent any hosts downstream of that LAN from 2400 receiving traffic. 2402 6. A forged State Refresh message on a multi-access LAN would have the 2403 same impact as a forged Assert message, having the same general 2404 functions. In addition, forged State Refresh messages would be 2405 propagated downstream and might be used in a denial of service 2406 attack. Therefore, a PIM-DM router SHOULD rate limit State Refresh 2407 messages propagated. 2409 7.2. Non-cryptographic Authentication Mechanisms 2411 A PIM-DM router SHOULD provide an option to limit the set of neighbors 2412 from which it will accept PIM-DM messages. Either static configuration 2413 of IP addresses or an IPSec security association may be used. All 2414 options that restrict the range of addresses from which packets are 2415 accepted MUST default to allowing all packets. 2417 Furthermore, a PIM router SHOULD NOT accept protocol messages from a 2418 router from which it has not yet received a valid Hello message. 2420 7.3. Authentication Using IPsec 2422 The IPSec [10] transport mode using the Authentication Header (AH) is 2423 the recommended method to prevent the above attacks in PIM. The 2424 specific AH authentication algorithm and parameters, including the 2425 choice of authentication algorithm and the choice of key, are configure 2426 by the network administrator. The Encapsulating Security Payload (ESP) 2427 MAY also be used to provide both encryption and authentication of PIM 2428 protocol messages. When IPsec authentication is used, a PIM router 2429 SHOULD reject (drop without processing) any unauthorized PIM protocol 2430 messages. 2432 To use IPSec, the administrator of a PIM network configures each PIM 2433 router with one or more Security Associations and associated Security 2434 Parameters Indices that are used by senders to sign PIM protocol 2435 messages and are used by receivers to authenticate received PIM protocol 2436 messages. This document does not describe protocols for establishing 2437 Security Associations. It assumes that manual configuration of Security 2438 Associations is performed, but it does not preclude the use of some 2439 future negotiation protocol such as GDOI [17] to establish Security 2440 Associations. 2442 The network administrator defines a Security Association (SA) and 2443 Security Parameters Index (SPI) that is to be used to authenticate all 2444 PIM-DM protocol messages from each router on each link in a PIM-DM 2445 domain. 2447 In order to avoid the problem of allocating individual keys for each 2448 neighbor on a link to each individual router, it is acceptable to 2449 establish only one authentication key for all PIM-DM routers on a link. 2450 This will not specifically authenticate the individual router sending 2451 the message, but will assure that the sender is a PIM-DM router on that 2452 link. If this method is used, the receiver of the message MUST ignore 2453 the received sequence number, thus disabling anti-replay mechanisms. 2454 The effects of disabling anti-replay mechanisms are essentially the same 2455 as the effects of forged messages described in section 7.1 with the 2456 additional protection that the forger can only reuse legitimate 2457 messages. 2459 The Security Policy Database at a PIM-DM router should be configured to 2460 ensure that all incoming and outgoing PIM-DM packets use the SA 2461 associated with the interface to which the packet is sent. Note that, 2462 according to [10], there is nominally a different Security Association 2463 Database (SAD) for each router interface. Thus, the selected Security 2464 Association for an inbound PIM-DM packet can vary depending on the 2465 interface on which the packet arrived. This fact allows the network 2466 administrator to use different authentication methods for each link, 2467 even though the destination address is the same for most PIM-DM packets, 2468 regardless of interface. 2470 7.4. Denial of Service Attacks 2472 There are a number of possible denial of service attacks against PIM 2473 that can be caused by generating false PIM protocol messages or even by 2474 generating false data traffic. Authenticating PIM protocol traffic 2475 prevents some, but not all of these attacks. The possible attacks 2476 include: 2478 * Sending packets to many different group addresses quickly can be a 2479 denial of service attack in and of itself. These messages will 2480 initially be flooded throughout the network before they are pruned 2481 back. The maintenance of state machines and State Refresh messages 2482 will be a continual drain on network resources. 2484 * Forged State Refresh messages sent quickly could be propagated by 2485 downstream routers, creating a potential denial of service attack. 2486 Therefore, a PIM-DM router SHOULD rate limit State Refresh messages 2487 propagated. 2489 8. Authors' Addresses 2491 Andrew Adams 2492 NextHop Technologies 2493 825 Victors Way, Suite 100 2494 Ann Arbor, MI 48108-2738 2495 ala@nexthop.com 2497 Jonathan Nicholas 2498 ITT Industries 2499 Aerospace/Communications Division 2500 100 Kingsland Rd 2501 Clifton, NJ 07014 2502 jonathan.nicholas@itt.com 2504 William Siadak 2505 NextHop Technologies 2506 825 Victors Way, Suite 100 2507 Ann Arbor, MI 48108-2738 2508 wfs@nexthop.com 2510 9. Acknowledgments 2512 The major features of PIM-DM were originally designed by Stephen 2513 Deering, Deborah Estrin, Dino Farinacci, Van Jacobson, Ahmed Helmy, 2514 David Meyer, and Liming Wei. Additional features for state refresh 2515 were designed by Dino Farinacci, Isidor Kouvelas and Kurt Windisch. 2516 This revision was undertaken to incorporate some of the lessons learned 2517 during the evolution of the PIM-SM specification and early deployments 2518 of PIM-DM. 2520 Thanks the PIM Working Group for their comments. 2522 10. References 2524 10.1 Normative References 2526 [1] S.E. Deering, "Host Extensions for IP Multicasting", March 1989, 2527 RFC 1112. 2529 [2] W.Fenner, "Internet Group Management Protocol, Version 2", 2530 November 1997, RFC 2236. 2532 [3] B. Cain, S. Deering, B. Fenner, I. Kouvelas, A. Thyagarajan, 2533 "Internet Group Management Protocol, Version 3", 2534 October 2002, RFC 3376. 2536 [4] D. Estrin, D. Farinacci, A. Helmy, D. Thaler, S. Deering, 2537 M. Handley, V. Jacobson, C. Liu, P. Sharma, L. Wei, "Protocol 2538 Independent Multicast-Sparse Mode (PIM-SM): Protocol 2539 Specification", June 1998, RFC 2362. 2541 [5] S. Deering, R. Hinden, "Internet Protocol, Version 6 (IPv6) 2542 Specification", December 1998, RFC 2460. 2544 [6] S. Deering, W. Fenner, B. Haberman, "Multicast Listener Discovery 2545 (MLD) for IPv6", October 1999, RFC 2710. 2547 [7] D. Thaler, "Interoperability Rules for Multicast Routing 2548 Protocols", October 1999, RFC 2715. 2550 [8] T. Narten, H. Alvestrand, "Guidelines for Writing an IANA 2551 Considerations Section in RFCs", October 1998, RFC 2434. 2553 [9] IANA, "Address Family Numbers", linked from 2554 http://www.iana.org/numbers.html. 2556 [10] S. Kent, R. Atkinson, "Security Architecture for the Internet 2557 Protocol", November 1998, RFC 2401. 2559 10.2 Informative References 2561 [11] S.E. Deering, "Multicast Routing in a Datagram Internetwork", 2562 Ph.D. Thesis, Electrical Engineering Dept., Stanford University, 2563 December 1991. 2565 [12] D. Waitzman, B.Partridge, S.Deering, "Distance Vector Multicast 2566 Routing Protocol", November 1988, RFC 1075 2568 [13] W. Fenner, M. Handley, H.Holbrook, I. Kouvelas, "Protocol 2569 Independent Multicast - Sparse Mode (PIM-SM): Protocol 2570 Specification (Revised)", draft-ietf-pim-sm-v2-new-09.txt, 2571 work in progress. 2573 [14] H.Holbrook, B. Cain, "Source Specific Multicast for IP", 2574 draft-ietf-ssm-arch-04.txt, work in progress. 2576 [15] K.McCloghrie, D.Farinacci, D.Thaler, B.Fenner, "Protocol 2577 Independent Multicast MIB for IPv4", October 2000, RFC 2934 2579 [16] M. Handley, I. Kouvelas, T. Speakman, L. Vicisano, "Bi-directional 2580 Protocol Independent Multicast", draft-ietf-pim-bidir-06.txt, 2581 work in progress. 2583 [17] M. Baugher, B. Weis, T. Hardjono, H. Harney, "The Group Domain of 2584 Interpretation", July 2003, RFC 3547. 2586 [18] W. Fenner, M. Handley, R. Kermode, D. Thaler, "Bootstrap Router 2587 (BSR) Mechanism for PIM Sparse Mode", draft-ietf-pim-sm-bsr-03.txt, 2588 work in progress. 2590 11. Full Copyright Statement 2592 Copyright (C) The Internet Society (2004). All Rights Reserved. 2594 This document and translations of it may be copied and furnished to 2595 others, and derivative works that comment on or otherwise explain it 2596 or assist in its implementation may be prepared, copied, published and 2597 distributed, in whole or in part, without restriction of any kind, 2598 provided that the above copyright notice and this paragraph are 2599 included on all such copies and derivative works. However, this 2600 document itself may not be modified in any way, such as by removing 2601 the copyright notice or references to the Internet Society or other 2602 internet organizations, except as needed for the purpose of 2603 developing Internet standards in which case the procedures for 2604 copyrights defined in the Internet Standards process must be 2605 followed, or as required to translate it into languages other than 2606 English. 2608 The limited permissions granted above are perpetual and will not be 2609 revoked by the Internet Society or its successors or assigns. 2611 This document and the information contained herein is provided on an 2612 "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING 2613 TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING 2614 BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION 2615 HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF 2616 MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 2618 Internet Engineering Task Force PIM WG 2619 INTERNET DRAFT Andrew Adams (NextHop Technolgies) 2620 draft-ietf-pim-dm-new-v2-05.txt Jonathan Nicholas (ITT A/CD) 2621 William Siadak (NextHop Technologies) 2622 June 2004 2623 Expires December 2004 2625 Protocol Independent Multicast - Dense Mode (PIM-DM): 2626 Protocol Specification (Revised) 2628 Status of this Document 2630 This document is an Internet Draft and is in full conformance with all 2631 provisions of Section 10 of RFC 2026. 2633 Internet Drafts are working documents of the Internet Engineering Task 2634 Force (IETF), its areas, and its working groups. Note that other groups 2635 may also distribute working documents as Internet Drafts. 2637 Internet Drafts are draft documents valid for a maximum of six months 2638 and may be updated, replaced, or obsoleted by other documents at any 2639 time. It is inappropriate to use Internet Drafts as reference material 2640 or to cite them other than as "work in progress." 2642 The list of current Internet Drafts can be accessed at 2643 http://www.ietf.org/ietf/lid-abstracts.txt. 2645 The list of Internet Draft Shadow Directories can be accessed at 2646 http://www.ietf.org/shadow.html. 2648 This document is a product of the IETF PIM WG. Comments should be 2649 addressed to the authors, or the WG's mailing list at pim@ietf.org. 2651 Copyright Notice 2653 Copyright (C) The Internet Society (2004). All Rights Reserved. 2655 Abstract 2657 This document specifies Protocol Independent Multicast - Dense Mode 2658 (PIM-DM). PIM-DM is a multicast routing protocol that uses the 2659 underlying unicast routing information base to flood multicast datagrams 2660 to all multicast routers. Prune messages are used to prevent future 2661 messages from propagating to routers with no group membership 2662 information. 2664 Table of Contents 2666 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 4 2667 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . 4 2668 2.1. Definitions . . . . . . . . . . . . . . . . . . . . . . . . 4 2669 2.2. Pseudocode Notation . . . . . . . . . . . . . . . . . . . . 5 2670 3. PIM-DM Protocol Overview . . . . . . . . . . . . . . . . . . 5 2671 4. Protocol Specification . . . . . . . . . . . . . . . . . . . 6 2672 4.1. PIM Protocol State . . . . . . . . . . . . . . . . . . . . . 6 2673 4.1.1. General Purpose State . . . . . . . . . . . . . . . . . . . 7 2674 4.1.2. (S,G) State . . . . . . . . . . . . . . . . . . . . . . . . 7 2675 4.1.3. State Summarization Macros . . . . . . . . . . . . . . . . . 8 2676 4.2. Data Packet Forwarding Rules . . . . . . . . . . . . . . . . 10 2677 4.3. Hello Messages . . . . . . . . . . . . . . . . . . . . . . . 10 2678 4.3.1. Sending Hello Messages . . . . . . . . . . . . . . . . . . . 10 2679 4.3.2. Receiving Hello Messages . . . . . . . . . . . . . . . . . . 11 2680 4.3.3. Hello Message Hold Time . . . . . . . . . . . . . . . . . . 11 2681 4.3.4. Handling Router Failures . . . . . . . . . . . . . . . . . . 11 2682 4.3.5. Reducing Prune Propagation Delay on LANs . . . . . . . . . . 12 2683 4.4. PIM-DM Prune, Join and Graft Messages . . . . . . . . . . . 13 2684 4.4.1. Upstream Prune, Join and Graft Messages . . . . . . . . . . 13 2685 4.4.1.1. Transitions from the Forwarding (F) State . . . . . . . . . 16 2686 4.4.1.2. Transitions from the Pruned (P) State . . . . . . . . . . . 17 2687 4.4.1.3. Transitions from the AckPending (AP) State . . . . . . . . . 18 2688 4.4.2. Downstream Prune, Join and Graft Messages . . . . . . . . . 19 2689 4.4.2.1. Transitions from the NoInfo State . . . . . . . . . . . . . 21 2690 4.4.2.2. Transitions from the PrunePending (PP) State . . . . . . . . 22 2691 4.4.2.3. Transitions from the Prune (P) State . . . . . . . . . . . . 23 2692 4.5. State Refresh . . . . . . . . . . . . . . . . . . . . . . . 24 2693 4.5.1. Forwarding of State Refresh Messages . . . . . . . . . . . . 24 2694 4.5.2. State Refresh Message Origination . . . . . . . . . . . . . 25 2695 4.5.2.1. Transitions from the NotOriginator (NO) State . . . . . . . 27 2696 4.5.2.2. Transitions from the Originator (O) State . . . . . . . . . 27 2697 4.6. PIM Assert Messages . . . . . . . . . . . . . . . . . . . . 28 2698 4.6.1. Assert Metrics . . . . . . . . . . . . . . . . . . . . . . . 28 2699 4.6.2. AssertCancel Messages . . . . . . . . . . . . . . . . . . . 29 2700 4.6.3. Assert State Macros . . . . . . . . . . . . . . . . . . . . 29 2701 4.6.4. (S,G) Assert Message State Machine . . . . . . . . . . . . . 29 2702 4.6.4.1. Transitions from NoInfo State . . . . . . . . . . . . . . . 31 2703 4.6.4.2. Transitions from Winner State . . . . . . . . . . . . . . . 32 2704 4.6.4.3. Transitions from Loser State . . . . . . . . . . . . . . . . 33 2705 4.6.5. Rationale for Assert Rules . . . . . . . . . . . . . . . . . 34 2706 4.7. PIM Packet Formats . . . . . . . . . . . . . . . . . . . . . 35 2707 4.7.1. PIM Header . . . . . . . . . . . . . . . . . . . . . . . . . 35 2708 4.7.2. Encoded Unicast Address . . . . . . . . . . . . . . . . . . 36 2709 4.7.3. Encoded Group Address . . . . . . . . . . . . . . . . . . . 36 2710 4.7.4. Encoded Source Address . . . . . . . . . . . . . . . . . . . 37 2711 4.7.5. Hello Message Format . . . . . . . . . . . . . . . . . . . . 38 2712 4.7.5.1. Hello Hold Time Option . . . . . . . . . . . . . . . . . . . 39 2713 4.7.5.2. LAN Prune Delay Option . . . . . . . . . . . . . . . . . . . 39 2714 4.7.5.3. Generation ID Option . . . . . . . . . . . . . . . . . . . . 40 2715 4.7.5.4. State Refresh Capable Option . . . . . . . . . . . . . . . . 40 2716 4.7.6. Join/Prune Message Format . . . . . . . . . . . . . . . . . 40 2717 4.7.7. Assert Message Format . . . . . . . . . . . . . . . . . . . 42 2718 4.7.8. Graft Message Format . . . . . . . . . . . . . . . . . . . . 43 2719 4.7.9. Graft Ack Message Format . . . . . . . . . . . . . . . . . . 43 2720 4.7.10. State Refresh Message Format . . . . . . . . . . . . . . . . 44 2721 4.8. PIM-DM Timers . . . . . . . . . . . . . . . . . . . . . . . 45 2722 5. Protocol Interaction Considerations . . . . . . . . . . . . 48 2723 5.1. PIM-SM Interactions . . . . . . . . . . . . . . . . . . . . 48 2724 5.2. IGMP Interactions . . . . . . . . . . . . . . . . . . . . . 49 2725 5.3. Source Specific Multicast (SSM) Interactions . . . . . . . . 49 2726 5.4. Multicast Group Scope Boundary Interactions . . . . . . . . 49 2727 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . 49 2728 6.1. PIM Address Family . . . . . . . . . . . . . . . . . . . . . 49 2729 6.2. PIM Hello Options . . . . . . . . . . . . . . . . . . . . . 50 2730 7. Security Considerations. . . . . . . . . . . . . . . . . . . 50 2731 7.1. Attacks Based on Forged Messages . . . . . . . . . . . . . . 50 2732 7.2. Non-cryptographic Authentication Mechanisms . . . . . . . . 51 2733 7.3. Authentication Using IPsec . . . . . . . . . . . . . . . . . 52 2734 7.4. Denial of Service Attacks . . . . . . . . . . . . . . . . . 53 2735 8. Authors' Addresses . . . . . . . . . . . . . . . . . . . . . 53 2736 9. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . 53 2737 10. References . . . . . . . . . . . . . . . . . . . . . . . . . 54 2738 10.1. Normative References . . . . . . . . . . . . . . . . . . . . 54 2739 10.2. Informative References . . . . . . . . . . . . . . . . . . . 54 2740 11. Full Copyright Statement . . . . . . . . . . . . . . . . . . 55 2741 1. Introduction 2743 This specification defines a multicast routing algorithm for multicast 2744 groups that are densely distributed across a network. This protocol 2745 does not have a topology discovery mechanism often used by a unicast 2746 routing protocol. It employs the same packet formats sparse mode PIM 2747 (PIM-SM) uses. This protocol is called PIM - Dense Mode. The 2748 foundation of this design was largely built on Deering's early work on 2749 IP multicast routing [11]. 2751 2. Terminology 2753 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 2754 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" are to be 2755 interpreted as described in RFC 2119 and indicate requirement levels for 2756 compliant PIM-DM implementations. 2758 2.1. Definitions 2760 Multicast Routing Information Base (MRIB) 2761 This is the multicast topology table, which is typically derived from 2762 the unicast routing table, or routing protocols such as MBGP that 2763 carry multicast-specific topology information. PIM-DM uses the MRIB 2764 to make decisions regarding RPF interfaces. 2766 Tree Information Base (TIB) 2767 This is the collection of state maintained by a PIM router and created 2768 by receiving PIM messages and IGMP information from local hosts. It 2769 essentially stores the state of all multicast distribution trees at 2770 that router. 2772 Reverse Path Forwarding (RPF) 2773 RPF is a multicast forwarding mode where a data packet is accepted for 2774 forwarding only if it is received on an interface used to reach the 2775 source in unicast. 2777 Upstream Interface 2778 Interface towards the source of the datagram. Also known as the RPF 2779 Interface. 2781 Downstream Interface 2782 All interfaces that are not the upstream interface, including the 2783 router itself. 2785 (S,G) Pair 2786 Source S and destination group G associated with an IP packet. 2788 2.2. Pseudocode Notation 2790 We use set notation in several places in this specification. 2792 A (+) B 2793 is the union of two sets A and B. 2795 A (-) B 2796 are the elements of set A that are not in set B. 2798 NULL 2799 is the empty set or list. 2801 Note that operations MUST be conducted in the order specified. This is 2802 due to the fact that (-) is not a true difference operator because B is 2803 not necessarily a subset of A. That is, A (+) B (-) C = A (-) C (+) B 2804 is not a true statement unless C is a subset of both A and B. 2806 In addition we use C-like syntax: 2807 = denotes assignment of a variable. 2808 == denotes a comparison for equality. 2809 != denotes a comparison for inequality. 2811 Braces { and } are used for grouping. 2813 3. PIM-DM Protocol Overview 2815 This section provides an overview of PIM-DM behavior. It is intended as 2816 an introduction to how PIM-DM works, and is NOT definitive. For the 2817 definitive specification, see Section 4 - Protocol Specification. 2819 PIM-DM assumes that when a source starts sending, all downstream systems 2820 want to receive multicast datagrams. Initially, multicast datagrams are 2821 flooded to all areas of the network. PIM-DM uses RPF to prevent looping 2822 of multicast datagrams while flooding. If some areas of the network do 2823 not have group members, PIM-DM will prune off the forwarding branch by 2824 instantiating prune state. 2826 Prune state has a finite lifetime. When that lifetime expires, data 2827 will again be forwarded down the previously pruned branch. 2829 Prune state is associated with an (S,G) pair. When a new member for a 2830 group G appears in a pruned area, a router can "graft" toward the source 2831 S for the group, thereby turning the pruned branch back into a 2832 forwarding branch. 2834 The broadcast of datagrams followed by pruning of unwanted branches is 2835 often referred to as a flood and prune cycle and is typical of dense 2836 mode protocols. 2838 In order to minimize repeated flooding of datagrams and subsequent 2839 pruning associated with a particular (S,G) pair, PIM-DM uses a state 2840 refresh message. This message is sent by the router(s) directly 2841 connected to the source and is propagated throughout the network. When 2842 received by a router on its RPF interface, the state refresh message 2843 causes an existing prune state to be refreshed. 2845 Compared with multicast routing protocols with built in topology 2846 discovery mechanisms (e.g. DVMRP [12]) PIM-DM has a simplified design 2847 and is not hard-wired into a specific topology discovery protocol. 2848 However, such a simplification does incur more overhead by causing 2849 flooding and pruning to occur on some links that could be avoided if 2850 sufficient topology information were available, i.e. to decide whether 2851 an interface leads to any downstream members of a particular group. 2852 Additional overhead is chosen in favor of the simplification and 2853 flexibility gained by not depending on a specific topology discovery 2854 protocol. 2856 PIM-DM differs from PIM-SM in two essential ways: 1) There are no 2857 periodic joins transmitted, only explicitly triggered prunes and grafts. 2858 2) There is no Rendezvous Point (RP). This is particularly important in 2859 networks that cannot tolerate a single point of failure. (An RP is the 2860 root of a shared multicast distribution tree. For more details see [4]). 2862 4. Protocol Specification 2864 The specification of PIM-DM is broken into several parts: 2866 * Section 4.1 details the protocol state stored. 2867 * Section 4.2 specifies the data packet forwarding rules. 2868 * Section 4.3 specifies generation and processing of Hello messages. 2869 * Section 4.4 specifies the Join, Prune and Graft generation and 2870 processing rules. 2871 * Section 4.5 specifies the State Refresh generation and forwarding 2872 rules. 2873 * Section 4.6 specifies the Assert generation and processing rules. 2874 * Section 4.7 gives details on PIM-DM Packet Formats. 2875 * Section 4.8 summarizes PIM-DM timers and their defaults. 2877 4.1. PIM Protocol State 2879 This section specifies all the protocol states that a PIM-DM 2880 implementation should maintain in order to function correctly. We term 2881 this state the Tree Information Base or TIB, as it holds the state of 2882 all the multicast distribution trees at this router. In this 2883 specification, we define PIM-DM mechanisms in terms of the TIB. 2884 However, only a very simple implementation would actually implement 2885 packet forwarding operations in terms of this state. Most 2886 implementations will use this state to build a multicast forwarding 2887 table, which would then be updated when the relevant state in the TIB 2888 changes. 2890 Unlike PIM-SM, PIM-DM does not maintain a keepalive timer associated 2891 with each (S,G) route. Within PIM-DM, route and state information 2892 associated with an (S,G) entry MUST be maintained as long as any timer 2893 associated with that (S,G) entry is active. When no timer associated 2894 with an (S,G) entry is active, all information concerning that (S,G) 2895 route may be discarded. 2897 Although we specify precisely the state to be kept, this does not mean 2898 that an implementation of PIM-DM needs to hold the state in this form. 2899 This is actually an abstract state definition, which is needed in order 2900 to specify the router's behavior. A PIM-DM implementation is free to 2901 hold whatever internal state it requires, and will still be conformant 2902 with this specification so long as it results in the same externally 2903 visible protocol behavior as an abstract router that holds the following 2904 state. 2906 4.1.1. General Purpose State 2908 A router stores the following non-group-specific state: 2910 For each interface: 2911 Hello Timer (HT) 2912 State Refresh Capable 2913 LAN Delay Enabled 2914 Propagation Delay (PD) 2915 Override Interval (OI) 2917 Neighbor State: 2918 For each neighbor: 2919 Information from neighbor's Hello 2920 Neighbor's Gen ID. 2921 Neighbor's LAN Prune Delay 2922 Neighbor's Override Interval 2923 Neighbor's State Refresh Capability 2924 Neighbor Liveness Timer (NLT) 2926 4.1.2. (S,G) State 2928 For every source/group pair (S,G), a router stores the following state: 2930 (S,G) state: 2931 For each interface: 2932 Local Membership: 2933 State: One of {"NoInfo", "Include"} 2935 PIM (S,G) Prune State: 2936 State: One of {"NoInfo" (NI), "Pruned" (P), "PrunePending" (PP)} 2937 Prune Pending Timer (PPT) 2938 Prune Timer (PT) 2940 (S,G) Assert Winner State: 2941 State: One of {"NoInfo" (NI), "I lost Assert" (L), 2942 "I won Assert" (W)} 2943 Assert Timer (AT) 2944 Assert winner's IP Address 2945 Assert winner's Assert Metric 2947 Upstream interface-specific: 2948 Graft/Prune State: 2949 State: One of {"NoInfo" (NI), "Pruned" (P), "Forwarding" (F), 2950 "AckPending" (AP) } 2951 GraftRetry Timer (GRT) 2952 Override Timer (OT) 2953 Prune Limit Timer (PLT) 2955 Originator State: 2956 Source Active Timer (SAT) 2957 State Refresh Timer (SRT) 2959 4.1.3. State Summarization Macros 2961 Using the state defined above, the following "macros" are defined and 2962 will be used in the descriptions of the state machines and pseudocode in 2963 the following sections. 2965 The most important macros are those defining the outgoing interface list 2966 (or "olist") for the relevant state. 2968 immediate_olist(S,G) = pim_nbrs (-) prunes(S,G) (+) 2969 ( pim_include(*,G) (-) pim_exclude(S,G) ) (+) 2970 pim_include(S,G) (-) lost_assert(S,G) (-) 2971 boundary(G) 2973 olist(S,G) = immediate_olist(S,G) (-) RPF_interface(S) 2975 The macros pim_include(*,G) and pim_include(S,G) indicate the interfaces 2976 to which traffic might be forwarded or not forwarded because of hosts 2977 that are local members on those interfaces. 2979 pim_include(*,G) = {all interfaces I such that: 2980 local_receiver_include(*,G,I)} 2981 pim_include(S,G) = {all interfaces I such that: 2982 local_receiver_include(S,G,I)} 2983 pim_exclude(S,G) = {all interfaces I such that: 2984 local_receiver_exclude(S,G,I)} 2986 The macro RPF_interface(S) returns the RPF interface for source S. That 2987 is to say, it returns the interface used to reach S as indicated by the 2988 MRIB. 2990 The macro local_receiver_include(S,G,I) is true if the IGMP module or 2991 other local membership mechanism has determined that there are local 2992 members on interface I that desire to receive traffic sent specifically 2993 by S to G. 2995 The macro local_receiver_include(*,G,I) is true if the IGMP module or 2996 other local membership mechanism has determined that there are local 2997 members on interface I that desire to receive all traffic sent to G. 2998 Note that this determination is expected to account for membership joins 2999 initiated on or by the router. 3001 The macro local_receiver_exclude(S,G,I) is true if 3002 local_receiver_include(*,G,I) is true but none of the local members 3003 desire to receive traffic from S. 3005 The set pim_nbrs is the set of all interfaces on which the router has at 3006 least one active PIM neighbor. 3008 The set prunes(S,G) is the set of all interfaces on which the router has 3009 received Prune(S,G) messages: 3011 prunes(S,G) = {all interfaces I such that 3012 DownstreamPState(S,G,I) is in Pruned state} 3014 The set lost_assert(S,G) is the set of all interfaces on which the 3015 router has lost an (S,G) Assert. 3017 lost_assert(S,G) = {all interfaces I such that 3018 lost_assert(S,G,I) == TRUE} 3020 boundary(G) = {all interfaces I with an administratively scoped 3021 boundary for group G} 3023 The following pseudocode macro definitions are also used in many places 3024 in the specification. Basically RPF' is the RPF neighbor towards a 3025 source unless a PIM-DM Assert has overridden the normal choice of 3026 neighbor. 3028 neighbor RPF'(S,G) { 3029 if ( I_Am_Assert_loser(S, G, RPF_interface(S) )) { 3030 return AssertWinner(S, G, RPF_interface(S) ) 3031 } else { 3032 return MRIB.next_hop( S ) 3033 } 3034 } 3036 The macro I_Am_Assert_loser(S, G, I) is true if the Assert state machine 3037 (in section 4.6) for (S,G) on interface I is in the "I am Assert Loser" 3038 state. 3040 4.2. Data Packet Forwarding Rules 3042 The PIM-DM packet forwarding rules are defined below in pseudocode. 3044 iif is the incoming interface of the packet. 3045 S is the source address of the packet. 3046 G is the destination address of the packet (group address). 3047 RPF_interface(S) is the interface the MRIB indicates would be used to 3048 route packets to S. 3050 First, an RPF check MUST be performed to determine whether the packet 3051 should be accepted based on TIB state and the interface on which that 3052 the packet arrived. Packets that fail the RPF check MUST NOT be 3053 forwarded and the router will conduct an assert process for the (S,G) 3054 pair specified in the packet. Packets for which a route to the source 3055 cannot be found MUST be discarded. 3057 If the RPF check has been passed, an outgoing interface list is 3058 constructed for the packet. If this list is not empty, then the packet 3059 MUST be forwarded to all listed interfaces. If the list is empty, then 3060 the router will conduct a prune process for the (S,G) pair specified in 3061 the packet. 3063 On receipt on a data packet from S addressed to G on interface iif: 3065 if (iif == RPF_interface(S) AND UpstreamPState(S,G) != Pruned) { 3066 oiflist = olist(S,G) 3067 } else { 3068 oiflist = NULL 3069 } 3070 forward packet on all interfaces in oiflist 3072 This pseudocode employs the following "macro" definition: 3074 UpstreamPState(S,G) is the state of the Upstream(S,G) state machine in 3075 section 4.4.1. 3077 4.3. Hello Messages 3079 This section describes the generation and processing of Hello messages. 3081 4.3.1. Sending Hello Messages 3083 PIM-DM uses Hello messages to detect other PIM routers. Hello messages 3084 are sent periodically on each PIM enabled interface. Hello messages are 3085 multicast to the ALL-PIM-ROUTERS group. When PIM is enabled on an 3086 interface or a router first starts, the Hello Timer (HT) MUST be set to 3087 random value between 0 and Triggered_Hello_Delay. This prevents 3088 synchronization of Hello messages if multiple routers are powered on 3089 simultaneously. 3091 After the initial Hello message, a Hello message MUST be sent every 3092 Hello_Period. A single Hello timer MAY be used to trigger sending 3093 Hello messages on all active interfaces. The Hello Timer SHOULD NOT be 3094 reset except when it expires. 3096 4.3.2. Receiving Hello Messages 3098 When a Hello message is received, the receiving router SHALL record the 3099 receiving interface, the sender and any information contained in 3100 recognized options. This information is retained for a number of 3101 seconds in the Hold Time field of the Hello Message. If a new Hello 3102 message is received from a particular neighbor N, the Neighbor Liveness 3103 Timer (NLT(N,I)) MUST be reset to the newly received Hello Holdtime. If 3104 a Hello message is received from a new neighbor, the receiving router 3105 SHOULD send its own Hello message after a random delay between 0 and 3106 Triggered_Hello_Delay. 3108 4.3.3. Hello Message Hold Time 3110 The Hold Time in the Hello Message should be set to a value that can 3111 reasonably be expected to keep the Hello active until a new Hello 3112 message is received. On most links, this will be 3.5 times the value of 3113 Hello_Period. 3115 If the Hold Time is set to '0xffff', the receiving router MUST NOT time 3116 out that Hello message. This feature might be used for on-demand links 3117 to avoid keeping the link up with periodic Hello messages. 3119 If a Hold Time of '0' is received, the corresponding neighbor state is 3120 expired immediately. When a PIM router takes an interface down or 3121 changes IP address, a Hello message with a zero Hold Time SHOULD be sent 3122 immediately (with the old IP address if the IP address is changed) to 3123 cause any PIM neighbors to remove the old information immediately. 3125 4.3.4. Handling Router Failures 3127 If a Hello message is received from an active neighbor with a different 3128 Generation ID (GenID), the neighbor has restarted and may not contain 3129 the correct (S,G) state. A Hello message SHOULD be sent after a random 3130 delay between 0 and Triggered_Hello_Delay (see 4.8) before any other 3131 messages are sent. If the neighbor is downstream, the router MAY 3132 replay the last State Refresh message for any (S,G) pairs for which it 3133 is the Assert Winner indicating Prune and Assert status to the 3134 downstream router. These State Refresh messages SHOULD be sent out 3135 immediately after the Hello message. If the neighbor is the upstream 3136 neighbor for an (S,G) entry, the router MAY cancel its Prune Limit 3137 Timer to permit sending a prune and reestablishing a Pruned state in the 3138 upstream router. 3140 Upon startup, a router MAY use any State Refresh messages received 3141 within Hello_Period of its first Hello message on an interface to 3142 establish state information. The State Refresh source will be the 3143 RPF'(S), and Prune status for all interfaces will be set according to 3144 the Prune Indicator bit in the State Refresh message. If the Prune 3145 Indicator is set, the router SHOULD set the PruneLimitTimer to 3146 Prune_Holdtime and set the PruneTimer on all downstream interfaces to 3147 the State Refresh's Interval times two. The router SHOULD then 3148 propagate the State Refresh as described in section 4.5.1. 3150 4.3.5. Reducing Prune Propagation Delay on LANs 3152 If all routers on a LAN support the LAN Prune Delay option, then the PIM 3153 routers on that LAN will use the values received to adjust their 3154 J/P_Override_Interval on that interface and the interface is LAN Delay 3155 Enabled. Briefly, to avoid synchronization of Prune Override (Join) 3156 messages when multiple downstream routers share a multi-access link, 3157 sending of such messages is delayed by a small random amount of time. 3158 The period of randomization is configurable and has a default value of 3 3159 seconds. 3161 Each router on the LAN expresses its view of the amount of randomization 3162 necessary in the Override Interval field of the LAN Prune Delay option. 3163 When all routers on a LAN use the LAN Prune Delay Option, all routers on 3164 the LAN MUST set their Override_Interval to the largest Override value 3165 on the LAN. 3167 The LAN Delay inserted by a router in the LAN Prune Delay option 3168 expresses the expected message propagation delay on the link and SHOULD 3169 be configurable by the system administrator. When all routers on a link 3170 use the LAN Prune Delay Option, all routers on the LAN MUST set 3171 Propagation Delay to the largest LAN Delay on the LAN. 3173 PIM implementers should enforce a lower bound on the permitted values 3174 for this delay to allow for scheduling and processing delays within 3175 their router. Such delays may cause received messages to be processed 3176 later as well as triggered messages to be sent later than intended. 3177 Setting this LAN Prune Delay to too low a value may result in temporary 3178 forwarding outages because a downstream router will not be able to 3179 override a neighbor's prune message before the upstream neighbor stops 3180 forwarding. 3182 4.4. PIM-DM Prune, Join and Graft Messages 3184 This section describes the generation and processing of PIM-DM Join, 3185 Prune and Graft messages. Prune messages are sent towards the upstream 3186 neighbor for S to indicate that traffic from S addressed to group G is 3187 not desired. In the case of two downstream routers A and B, where A 3188 wishes to continue receiving data and B does not, A will send a Join in 3189 response to B's Prune to override the Prune. This is the only situation 3190 in PIM-DM in which a Join message is used. Finally, a Graft message is 3191 used to re-join a previously pruned branch to the delivery tree. 3193 4.4.1. Upstream Prune, Join and Graft Messages 3195 The Upstream(S,G) state machine for sending Prune, Graft and Join 3196 messages is given below. There are three states. 3198 Forwarding (F) 3199 This is the starting state of the Upsteam(S,G) state machine. The 3200 state machine is in this state if it just started or if 3201 oiflist(S,G) != NULL. 3203 Pruned(P) 3204 The set, olist(S,G), is empty. The router will not forward data 3205 from S addressed to group G. 3207 AckPending(AP) 3208 The router was in the Pruned(P) state but a transition has occurred 3209 in the Downstream(S,G) state machine for one of this (S,G) entry's 3210 outgoing interfaces indicating that traffic from S addressed to G 3211 should again be forwarded. A Graft message has been sent to RPF'(S) 3212 but a Graft Ack message has not yet been received. 3214 In addition there are three state-machine-specific timers: 3216 GraftRetry Timer (GRT(S,G)) 3217 This timer is set when a Graft is sent upstream. If a corresponding 3218 GraftAck is not received before the timer expires, then another 3219 Graft is sent and the GraftRetry Timer is reset. The timer is 3220 stopped when a Graft Ack message is received. This timer is normally 3221 set to Graft_Retry_Period (see 4.8). 3223 Override Timer (OT(S,G)) 3224 This timer is set when a Prune(S,G) is received on the upstream 3225 interface where olist(S,G) != NULL. When the timer expires, a 3226 Join(S,G) message is sent on the upstream interface. This timer is 3227 normally set to t_override (see 4.8). 3229 Prune Limit Timer (PLT(S,G)) 3230 This timer is used to rate-limit Prunes on a LAN. It is only used 3231 when the Upstream(S,G) state machine is in the Pruned state. A Prune 3232 cannot be sent if this timer is running. This timer is normally set 3233 to t_limit (see 4.8). 3235 +-------------+ +-------------+ 3236 | | olist == NULL | | 3237 | Forward |----------------------->| Pruned | 3238 | | | | 3239 +-------------+ +-------------+ 3240 ^ | ^ | 3241 | | | | 3242 | |RPF`(S) Changes olist == NULL| | 3243 | | | | 3244 | | +-------------+ | | 3245 | +-------->| |----------+ | 3246 | | AckPending | | 3247 +-------------| |<-------------+ 3248 Rcv GraftAck OR +-------------+ olist != NULL 3249 Rcv State Refresh 3250 With (P==0) OR 3251 S Directly Connect 3253 Figure 1: Upstream Interface State Machine 3255 In tabular form, the state machine is defined as follows: 3257 +-------------------------------+--------------------------------------+ 3258 | | Previous State | 3259 | +------------+------------+------------+ 3260 | Event | Forwarding | Pruned | AckPending | 3261 +-------------------------------+------------+------------+------------+ 3262 | Data packet arrives on | ->P Send | ->P Send | N/A | 3263 | RPF_Interface(S) AND | Prune(S,G) | Prune(S,G) | | 3264 | olist(S,G) == NULL AND |Set PLT(S,G)|Set PLT(S,G)| | 3265 | PLT(S,G) not running | | | | 3266 +-------------------------------+------------+------------+------------+ 3267 | State Refresh(S,G) received | ->F Set | ->P Reset |->AP Set | 3268 | from RPF`(S) AND | OT(S,G) | PLT(S,G) | OT(S,G) | 3269 | Prune Indicator == 1 | | | | 3270 +-------------------------------+------------+------------+------------+ 3271 | State Refresh(S,G) received | ->F | ->P Send |->F Cancel | 3272 | from RPF`(S) AND | | Prune(S,G) | GRT(S,G) | 3273 | Prune Indicator == 0 AND | |Set PLT(S,G)| | 3274 | PLT(S,G) not running | | | | 3275 +-------------------------------+------------+------------+------------+ 3276 | See Join(S,G) to RPF'(S) | ->F Cancel | ->P |->AP Cancel | 3277 | | OT(S,G) | | OT(S,G) | 3278 +-------------------------------+------------+------------+------------+ 3279 | See Prune(S,G) | ->F Set | ->P |->AP Set | 3280 | | OT(S,G) | | OT(S,G) | 3281 +-------------------------------+------------+------------+------------+ 3282 | OT(S,G) Expires | ->F Send | N/A |->AP Send | 3283 | | Join(S,G) | | Join(S,G) | 3284 +-------------------------------+------------+------------+------------+ 3285 +-------------------------------+--------------------------------------+ 3286 | | Previous State | 3287 | +------------+------------+------------+ 3288 | Event | Forwarding | Pruned | AckPending | 3289 +-------------------------------+------------+------------+------------+ 3290 | olist(S,G)->NULL | ->P Send | N/A |->P Send | 3291 | | Prune(S,G) | | Prune(S,G) | 3292 | |Set PLT(S,G)| |Set PLT(S,G)| 3293 | | | | Cancel | 3294 | | | | GRT(S,G) | 3295 +-------------------------------+------------+------------+------------+ 3296 | olist(S,G)->non-NULL | N/A | ->AP Send | N/A | 3297 | | | Graft(S,G) | | 3298 | | |Set GRT(S,G)| | 3299 +-------------------------------+------------+------------+------------+ 3300 | RPF'(S) Changes AND | ->AP Send | ->AP Send |->AP Send | 3301 | olist(S,G) != NULL | Graft(S,G) | Graft(S,G) | Graft(S,G) | 3302 | |Set GRT(S,G)|Set GRT(S,G)|Set GRT(S,G)| 3303 +-------------------------------+------------+------------+------------+ 3304 | RPF'(S) Changes AND | ->P | ->P Cancel |->P Cancel | 3305 | olist(S,G) == NULL | | PLT(S,G) | GRT(S,G) | 3306 +-------------------------------+------------+------------+------------+ 3307 | S becomes directly connected | ->F | ->P |->F Cancel | 3308 | | | | GRT(S,G) | 3309 +-------------------------------+------------+------------+------------+ 3310 | GRT(S,G) Expires | N/A | N/A |->AP Send | 3311 | | | | Graft(S,G) | 3312 | | | |Set GRT(S,G)| 3313 +-------------------------------+------------+------------+------------+ 3314 | Receive GraftAck(S,G) from | ->F | ->P |->F Cancel | 3315 | RPF'(S) | | | GRT(S,G) | 3316 +-------------------------------+------------+------------+------------+ 3318 The transition event "RcvGraftAck(S,G)" implies receiving a Graft Ack 3319 message targeted to this router's address on the incoming interface for 3320 the (S,G) entry. If the destination address is not correct, the state 3321 transitions in this state machine must not occur. 3323 4.4.1.1. Transitions from the Forwarding (F) State 3325 When the Upstream(S,G) state machine is in the Forwarding (F) state, the 3326 following events may trigger a transition: 3328 Data Packet arrives on RPF_Interface(S) AND olist(S,G) == NULL AND S 3329 NOT directly connected 3330 The Upstream(S,G) state machine MUST transition to the Pruned (P) 3331 state, send a Prune(S,G) to RPF'(S) and set PLT(S,G) to t_limit 3332 seconds. 3334 State Refresh(S,G) Received from RPF'(S) 3335 The Upstream(S,G) state machine remains in a Forwarding state. If 3336 the received State Refresh has the Prune Indicator bit set to one, 3337 this router must override the upstream router's Prune state after a 3338 short random interval. If OT(S,G) is not running and the Prune 3339 Indicator bit equals one, the router MUST set OT(S,G) to t_override 3340 seconds. 3342 See Join(S,G) to RPF'(S) 3343 This event is only relevant if RPF_interface(S) is a shared medium. 3344 This router sees another router on RPF_interface(S) send a Join(S,G) 3345 to RPF'(S,G). If the OT(S,G) is running, then it means that the 3346 router had scheduled a Join to override a previously received Prune. 3347 Another router has responded more quickly with a Join and so the 3348 local router SHOULD cancel its OT(S,G), if it is running. The 3349 Upstream(S,G) state machine remains in the Forwarding (F) state. 3351 See Prune(S,G) AND S NOT directly connected 3352 This event is only relevant if RPF_interface(S) is a shared medium. 3353 This router sees another router on RPF_interface(S) send a 3354 Prune(S,G). As this router is in Forwarding state, it must 3355 override the Prune after a short random interval. If OT(S,G) is not 3356 running, the router MUST set OT(S,G) to t_override seconds. The 3357 Upstream(S,G) state machine remains in Forwarding (F) state. 3359 OT(S,G) Expires AND S NOT directly connected 3360 The OverrideTimer (OT(S,G)) expires. The router MUST send a 3361 Join(S,G) to RPF'(S) to override a previously detected prune. The 3362 Upstream(S,G) state machine remains in the Forwarding (F) state. 3364 olist(S,G) -> NULL AND S NOT directly connected 3365 The Upstream(S,G) state machine MUST transition to the Pruned (P) 3366 state, send a Prune(S,G) to RPF'(S) and set PLT(S,G) to t_limit 3367 seconds. 3369 RPF'(S) Changes AND olist(S,G) is non-NULL AND S NOT directly 3370 connected 3371 Unicast routing or Assert state causes RPF'(S) to change, including 3372 changes to RPF_Interface(S). The Upstream(S,G) state machine MUST 3373 transition to the AckPending (AP) state, unicast a Graft to the new 3374 RPF'(S) and set the GraftRetry Timer (GRT(S,G)) to 3375 Graft_Retry_Period. 3377 RPF'(S) Changes AND olist(S,G) is NULL 3378 Unicast routing or Assert state causes RPF'(S) to change, including 3379 changes to RPF_Interface(S). The Upstream(S,G) state machine MUST 3380 transition to the Pruned (P) state. 3382 4.4.1.2. Transitions from the Pruned (P) State 3384 When the Upstream(S,G) state machine is in the Pruned (P) state, the 3385 following events may trigger a transition: 3387 Data arrives on RPF_interface(S) AND PLT(S,G) not running AND S NOT 3388 directly connected 3389 Either another router on the LAN desires traffic from S addressed to 3390 G or a previous Prune was lost. In order to prevent generating a 3391 Prune(S,G) in response to every data packet, the PruneLimit Timer 3392 (PLT(S,G)) is used. Once the PLT(S,G) expires, the router needs to 3393 send another prune in response to a data packet not received 3394 directly from the source. A Prune(S,G) MUST be sent to RPF'(S) and 3395 the PLT(S,G) MUST be set to t_limit. 3397 State Refresh(S,G) Received from RPF'(S) 3398 The Upstream(S,G) state machine remains in a Pruned state. If the 3399 State Refresh has its Prune Indicator bit set to zero and PLT(S,G) 3400 is not running, a Prune(S,G) MUST be sent to RPF'(S) and the 3401 PLT(S,G) MUST be set to t_limit. If the State Refresh has its Prune 3402 Indicator bit set to one, the router MUST reset PLT(S,G) to t_limit. 3404 See Prune(S,G) to RPF'(S) 3405 A Prune(S,G) is seen on RPF_interface(S) to RPF'(S). The 3406 Upstream(S,G) state machine stays in the Pruned (P) state. The 3407 router MAY reset its PLT(S,G) to the value in the Holdtime field of 3408 the received message if greater than the current value of the 3409 PLT(S,G). 3411 olist(S,G)->non-NULL AND S NOT directly connected 3412 The set of interfaces defined by the olist(S,G) macro becomes 3413 non-empty indicating traffic from S addressed to group G must be 3414 forwarded. The Upstream(S,G) state machine MUST cancel PLT(S,G), 3415 transition to the AckPending (AP) state and unicast a Graft message 3416 to RPF'(S). The Graft Retry Timer (GRT(S,G)) MUST be set to 3417 Graft_Retry_Period. 3419 RPF'(S) Changes AND olist(S,G) == non-NULL AND S NOT directly 3420 connected 3421 Unicast routing or Assert state causes RPF'(S) to change, including 3422 changes to RPF_Interface(S). The Upstream(S,G) state machine MUST 3423 cancel PLT(S,G), transition to the AckPending (AP) state, send a 3424 Graft unicast to the new RPF'(S) and set the GraftRetry Timer 3425 (GRT(S,G)) to Graft_Retry_Period. 3427 RPF'(S) Changes AND olist(S,G) == NULL AND S NOT directly connected 3428 Unicast routing or Assert state causes RPF'(S) to change, including 3429 changes to RPF_Interface(S). The Upstream(S,G) state machine stays 3430 in the Pruned (P) state and MUST cancel the PLT(S,G) timer. 3432 S becomes directly connected 3433 Unicast routing changed so that S is directly connected. The 3434 Upstream(S,G) state machine remains in the Pruned (P) state. 3436 4.4.1.3. Transitions from the AckPending (AP) State 3438 When the Upstream(S,G) state machine is in the AckPending (AP) state, 3439 the following events may trigger a transition: 3441 State Refresh(S,G) Received from RPF'(S) with Prune Indicator == 1 3442 The Upstream(S,G) state machine remains in an AckPending state. The 3443 router must override the upstream router's Prune state after a short 3444 random interval. If OT(S,G) is not running and the Prune Indicator 3445 bit equals one, the router MUST set OT(S,G) to t_override seconds. 3447 State Refresh(S,G) Received from RPF'(S) with Prune Indicator == 0 3448 The router MUST cancel its GraftRetry Timer (GRT(S,G)) and 3449 transition to the Forwarding (F) state. 3451 See Join(S,G) to RPF'(S,G) 3452 This event is only relevant if RPF_interface(S) is a shared medium. 3453 This router sees another router on RPF_interface(S) send a Join(S,G) 3454 to RPF'(S,G). If the OT(S,G) is running, then it means that the 3455 router had scheduled a Join to override a previously received Prune. 3456 Another router has responded more quickly with a Join and so the 3457 local router SHOULD cancel its OT(S,G), if it is running. The 3458 Upstream(S,G) state machine remains in the AckPending (AP) state. 3460 See Prune(S,G) 3461 This event is only relevant if RPF_interface(S) is a shared medium. 3462 This router sees another router on RPF_interface(S) send a 3463 Prune(S,G). As this router is in AckPending (AP) state, it must 3464 override the Prune after a short random interval. If OT(S,G) is not 3465 running, the router MUST set OT(S,G) to t_override seconds. The 3466 Upstream(S,G) state machine remains in AckPending (AP) state. 3468 OT(S,G) Expires 3469 The OverrideTimer (OT(S,G)) expires. The router MUST send a 3470 Join(S,G) to RPF'(S). The Upstream(S,G) state machine remains in 3471 the AckPending (AP) state. 3473 olist(S,G) -> NULL 3474 The set of interfaces defined by the olist(S,G) macro becomes null 3475 indicating traffic from S addressed to group G should no longer be 3476 forwarded. The Upstream(S,G) state machine MUST transition to the 3477 Pruned (P) state. A Prune(S,G) MUST be multicast to the 3478 RPF_interface(S) with RPF'(S) named in the upstream neighbor field. 3479 The GraftRetry Timer (GRT(S,G)) MUST be cancelled and PLT(S,G) MUST 3480 be set to t_limit seconds. 3482 RPF'(S) Changes AND olist(S,G) does not become NULL AND S NOT directly 3483 connected 3484 Unicast routing or Assert state causes RPF'(S) to change, including 3485 changes to RPF_Interface(S). The Upstream(S,G) state machine stays 3486 in the AckPending (AP) state. A Graft MUST be unicast to the new 3487 RPF'(S) and the GraftRetry Timer (GRT(S,G)) reset to 3488 Graft_Retry_Period. 3490 RPF'(S) Changes AND olist(S,G) == NULL AND S NOT directly connected 3491 Unicast routing or Assert state causes RPF'(S) to change, including 3492 changes to RPF_Interface(S). The Upstream(S,G) state machine MUST 3493 transition to the Pruned (P) state. The GraftRetry Timer (GRT(S,G)) 3494 MUST be cancelled. 3496 S becomes directly connected 3497 Unicast routing has changed so that S is directly connected. The 3498 GraftRetry Timer MUST be cancelled and the Upstream(S,G) state 3499 machine MUST transition to the Forwarding(F) state. 3501 GRT(S,G) Expires 3502 The GraftRetry Timer (GRT(S,G)) expires for this (S,G) entry. The 3503 Upstream(S,G) state machine stays in the AckPending (AP) state. 3504 Another Graft message for (S,G) SHOULD be unicasted to RPF'(S) and 3505 the GraftRetry Timer (GRT(S,G)) reset to Graft_Retry_Period. It is 3506 RECOMMENDED that the router retry a configured number of times 3507 before ceasing retries. 3509 See GraftAck(S,G) from RPF'(S) 3510 A GraftAck is received from RPF'(S). The GraftRetry Timer MUST be 3511 cancelled and the Upstream(S,G) state machine MUST transition to the 3512 Forwarding(F) state. 3514 4.4.2 Downstream Prune, Join and Graft Messages 3516 The Prune(S,G) Downstream state machine for receiving Prune, Join and 3517 Graft messages on interface I is given below. This state machine MUST 3518 always be in the NoInfo state on the upstream interface. It contains 3519 three states. 3521 NoInfo(NI) 3522 The interface has no (S,G) Prune state and neither the Prune timer 3523 (PT(S,G,I)) nor the PrunePending timer ((PPT(S,G,I)) is running. 3525 PrunePending(PP) 3526 The router has received a Prune(S,G) on this interface from a 3527 downstream neighbor and is waiting to see whether the prune will be 3528 overridden by another downstream router. For forwarding purposes, 3529 the PrunePending state functions exactly like the NoInfo state. 3531 Pruned(P) 3532 The router has received a Prune(S,G) on this interface from a 3533 downstream neighbor and the Prune was not overridden. Data from S 3534 addressed to group G is no longer being forwarded on this interface. 3536 In addition there are two timers: 3538 PrunePending Timer (PPT(S,G,I)) 3539 This timer is set when a valid Prune(S,G) is received. Expiry of 3540 the PrunePending Timer (PPT(S,G,I)) causes the interface to 3541 transition to the Pruned state. 3543 Prune Timer (PT(S,G,I)) 3544 This timer is set when the PrunePending Timer (PT(S,G,I)) expires. 3545 Expiry of the Prune Timer (PT(S,G,I)) causes the interface to 3546 transition to the NoInfo (NI) state, thereby allowing data from S 3547 addressed to group G to be forwarded on the interface. 3549 +-------------+ +-------------+ 3550 | | PPT Expires | | 3551 |PrunePending |----------------------->| Pruned | 3552 | | | | 3553 +-------------+ +-------------+ 3554 | ^ | 3555 | | | 3556 | |Rcv Prune | 3557 | | | 3558 | | +-------------+ | 3559 | +---------| | | 3560 | | NoInfo |<-------------+ 3561 +------------>| | Rcv Join/Graft OR 3562 Rcv Join/Graft OR +-------------+ PT Expires OR 3563 RPF_Interface(S)->I RPF_Interface(S)->I 3565 Figure 2: Downstream Interface State Machine 3567 In tabular form, the state machine is: 3569 +-------------------------------+--------------------------------------+ 3570 | | Previous State | 3571 + +------------+------------+------------+ 3572 | Event | No Info | PrunePend | Pruned | 3573 +-------------------------------+------------+------------+------------+ 3574 | Receive Prune(S,G) |->PP Set |->PP |->P Reset | 3575 | | PPT(S,G,I) | | PT(S,G,I) | 3576 +-------------------------------+------------+------------+------------+ 3577 | Receive Join(S,G) |->NI |->NI Cancel |->NI Cancel | 3578 | | | PPT(S,G,I) | PT(S,G,I) | 3579 +-------------------------------+------------+------------+------------+ 3580 | Receive Graft(S,G) |->NI Send |->NI Send |->NI Send | 3581 | | GraftAck | GraftAck | GraftAck | 3582 | | | Cancel | Cancel | 3583 | | | PPT(S,G,I) | PT(S,G,I) | 3584 +-------------------------------+------------+------------+------------+ 3585 | PPT(S,G) Expires | N/A |->P Set | N/A | 3586 | | | PT(S,G,I) | | 3587 +-------------------------------+------------+------------+------------+ 3588 | PT(S,G) Expires | N/A | N/A |->NI | 3589 +-------------------------------+------------+------------+------------+ 3590 | RPF_Interface(S) becomes I |->NI |->NI Cancel |->NI Cancel | 3591 | | | PPT(S,G,I) | PT(S,G,I) | 3592 +-------------------------------+------------+------------+------------+ 3593 | Send State Refresh(S,G) out I |->NI |->PP |->P Reset | 3594 | | | | PT(S,G,I) | 3595 +-------------------------------+------------+------------+------------+ 3597 The transition events "Receive Graft(S,G)", "Receive Prune(S,G)" and 3598 "Receive Join(S,G)" denote receiving a Graft, Prune or Join message in 3599 which this router's address on I is contained in the message's upstream 3600 neighbor field. If the upstream neighbor field does not match this 3601 router's address on I, then these state transitions in this state 3602 machine must not occur. 3604 4.4.2.1. Transitions from the NoInfo State 3606 When the Prune(S,G) Downstream state machine is in the NoInfo (NI) 3607 state, the following events may trigger a transition: 3609 Receive Prune(S,G) 3610 A Prune(S,G) is received on interface I with the upstream neighbor 3611 field set to the router's address on I. The Prune(S,G) Downstream 3612 state machine on interface I MUST transition to the PrunePending 3613 (PP) state. The PrunePending Timer (PPT(S,G,I)) MUST be set to 3614 J/P_Override_Interval if the router has more than one neighbor on I. 3615 If the router has only one neighbor on interface I, then it SHOULD 3616 set the PPT(S,G,I) to zero, effectively transitioning immediately to 3617 the Pruned (P) state. 3619 Receive Graft(S,G) 3620 A Graft(S,G) is received on the interface I with the upstream 3621 neighbor field set to the router's address on I. The Prune(S,G) 3622 Downstream state machine on interface I stays in the NoInfo (NI) 3623 state. A GraftAck(S,G) MUST be unicasted to the originator of the 3624 Graft(S,G) message. 3626 4.4.2.2. Transitions from the PrunePending (PP) State 3628 When the Prune(S,G) downstream state machine is in the PrunePending (PP) 3629 state, the following events may trigger a transition. 3631 Receive Join(S,G) 3632 A Join(S,G) is received on interface I with the upstream neighbor 3633 field set to the router's address on I. The Prune(S,G) Downstream 3634 state machine on interface I MUST transition to the NoInfo (NI) 3635 state. The PrunePending Timer (PPT(S,G,I)) MUST be cancelled. 3637 Receive Graft(S,G) 3638 A Graft(S,G) is received on interface I with the upstream neighbor 3639 field set to the router's address on I. The Prune(S,G) Downstream 3640 state machine on interface I MUST transition to the NoInfo (NI) 3641 state and MUST unicast a Graft Ack message to the Graft originator. 3642 The PrunePending Timer (PPT(S,G,I)) MUST be cancelled. 3644 PPT(S,G,I) Expires 3645 The PrunePending Timer (PPT(S,G,I)) expires indicating that no 3646 neighbors have overridden the previous Prune(S,G) message. The 3647 Prune(S,G) Downstream state machine on interface I MUST transition 3648 to the Pruned (P) state. The Prune Timer (PT(S,G,I)) is started and 3649 MUST be initialized to the received Prune_Hold_Time minus 3650 J/P_Override_Interval. A PruneEcho(S,G) MUST be sent on I if I has 3651 more than one PIM neighbor. A PruneEcho(S,G) is simply a Prune(S,G) 3652 message multicast by the upstream router to a LAN with itself as the 3653 Upstream Neighbor. Its purpose is to add additional reliability so 3654 that if a Join that should have overridden the Prune is lost locally 3655 on the LAN, then the PruneEcho(S,G) may be received and trigger a 3656 new Join message . A PruneEcho(S,G) is OPTIONAL on an interface 3657 with only one PIM neighbor. In addition, the router MUST evaluate 3658 any possible transitions in the Upstream(S,G) state machine. 3660 RPF_Interface(S) becomes interface I 3661 The upstream interface for S has changed. The Prune(S,G) Downstream 3662 state machine on interface I MUST transition to the NoInfo (NI) 3663 state. The PrunePending Timer (PPT(S,G,I)) MUST be cancelled. 3665 4.4.2.3. Transitions from the Prune (P) State 3667 When the Prune(S,G) Downstream state machine is in the Pruned (P) state, 3668 the following events may trigger a transition. 3670 Receive Prune(S,G) 3671 A Prune(S,G) is received on the interface I with the upstream 3672 neighbor field set to the router's address on I. The Prune(S,G) 3673 Downstream state machine on interface I remains in the Pruned (P) 3674 state. The Prune Timer (PT(S,G,I)) SHOULD be reset to the holdtime 3675 contained in the Prune(S,G) message if it is greater than the 3676 current value. 3678 Receive Join(S,G) 3679 A Join(S,G) is received on the interface I with the upstream 3680 neighbor field set to the router's address on I. The Prune(S,G) 3681 downstream state machine on interface I MUST transition to the 3682 NoInfo (NI) state. The Prune Timer (PT(S,G,I)) MUST be cancelled. 3683 The router MUST evaluate any possible transitions in the 3684 Upstream(S,G) state machine. 3686 Receive Graft(S,G) 3687 A Graft(S,G) is received on interface I with the upstream neighbor 3688 field set to the router's address on I. The Prune(S,G) Downstream 3689 state machine on interface I MUST transition to the NoInfo (NI) 3690 state and send a Graft Ack back to the Graft's source. The Prune 3691 Timer (PT(S,G,I)) MUST be cancelled. The router MUST evaluate any 3692 possible transitions in the Upstream(S,G) state machine. 3694 PT(S,G,I) Expires 3695 The Prune Timer (PT(S,G,I)) expires indicating that it is again time 3696 to flood data from S addressed to group G onto interface I. The 3697 Prune(S,G) Downstream state machine on interface I MUST transition 3698 to the NoInfo (NI) state. The router MUST evaluate any possible 3699 transitions in the Upstream(S,G) state machine. 3701 RPF_Interface(S) becomes interface I 3702 The upstream interface for S has changed. The Prune(S,G) Downstream 3703 state machine on interface I MUST transition to the NoInfo (NI) 3704 state. The PruneTimer (PT(S,G,I)) MUST be cancelled. 3706 Send State Refresh(S,G) out interface I 3707 The router has refreshed the Prune(S,G) state on interface I. The 3708 router MUST reset the Prune Timer (PT(S,G,I)) to the Holdtime from 3709 an active Prune received on interface I. The Holdtime used SHOULD 3710 be the largest active one, but MAY be the most recently received 3711 active Prune Holdtime. 3713 4.5. State Refresh 3715 This section describes the major portions of the state refresh 3716 mechanism. 3718 4.5.1. Forwarding of State Refresh Messages 3720 When a State Refresh message, SRM, is received, it is forwarded 3721 according to the following pseudo-code. 3723 if (iif != RPF_interface(S)) 3724 return; 3725 if (RPF'(S) != srcaddr(SRM)) 3726 return; 3727 if (StateRefreshRateLimit(S,G) == TRUE) 3728 return; 3730 for each interface I in pim_nbrs { 3731 if (TTL(SRM) == 0 OR (TTL(SRM) - 1) < Threshold(I)) 3732 continue; /* Out of TTL, skip this interface */ 3733 if (boundary(I,G)) 3734 continue; /* This interface is scope boundary, skip it */ 3735 if (I == iif) 3736 continue; /* This is the incoming interface, skip it */ 3737 if (lost_assert(S,G,I) == TRUE) 3738 continue; /* Let the Assert Winner do State Refresh */ 3740 Copy SRM to SRM'; /* Make a copy of SRM to forward */ 3742 if (I contained in prunes(S,G)) { 3743 set Prune Indicator bit of SRM' to 1; 3745 if StateRefreshCapable(I) == TRUE 3746 set PT(S,G) to largest active holdtime read from a Prune message 3747 accepted on I; 3749 } else { 3750 set Prune Indicator bit of SRM' to 0; 3751 } 3753 set srcaddr(SRM') to my_addr(I); 3754 set TTL of SRM' to TTL(SRM) - 1; 3755 set metric of SRM' to metric of unicast route used to reach S; 3756 set pref of SRM' to preference of unicast route used to reach S; 3757 set mask of SRM' to mask of route used to reach S; 3758 if (AssertState == NoInfo) { 3759 set Assert Override of SRM' to 1; 3760 } else { 3761 set Assert Override of SRM' to 0; 3762 } 3764 transmit SRM' on I; 3765 } 3767 The pseudocode above employs the following macro definitions. 3769 Boundary(I,G) evaluates to TRUE if an administratively scoped boundary 3770 for group G is configured on interface I. 3772 StateRefreshCapable(I) evaluates to TRUE if all neighbors on an 3773 interface use the State Refresh option. 3775 StateRefreshRateLimit(S,G) evaluates to TRUE if the time elapsed since 3776 the last received StateRefresh(S,G) is less than the configured 3777 RefreshLimitInterval. 3779 TTL(SRM) returns the TTL contained in the State Refresh Message, SRM. 3780 This is different from the TTL contained in the IP header. 3782 Threshold(I) returns the minimum TTL that a packet must have before it 3783 can be transmitted on interface I. 3785 srcaddr(SRM) returns the source address contained in the network 3786 protocol (e.g. IPv4) header of the State Refresh Message, SRM. 3788 my_addr(I) returns this node's network (e.g. IPv4) address on interface 3789 I. 3791 4.5.2 State Refresh Message Origination 3793 This section describes the origination of State Refresh messages. These 3794 messages are generated periodically by the PIM-DM router that is 3795 directly connected to a source. One Origination(S,G) state machine 3796 exists per (S,G) entry in a PIM-DM router. 3798 The Origination(S,G) state machine has the following states: 3800 NotOriginator(NO) 3801 This is the starting state of the Origination(S,G) state machine. 3802 While in this state a router will not originate State Refresh 3803 messages for the (S,G) pair. 3805 Originator(O) 3806 When in this state the router will periodically originate State 3807 Refresh messages. Only routers which are directly connected to S 3808 may transition to this state. 3810 In addition there are two state-machine-specific timers: 3812 State Refresh Timer (SRT(S,G)) 3813 This timer is controls when State Refresh messages are generated. 3814 The timer is initially set when that Origination(S,G) state machine 3815 transitions to the O state. It is cancelled when the 3816 Origination(S,G) state machine transitions to the NO state. This 3817 timer is normally set to StateRefreshInterval (see 4.8). 3819 Source Active Timer (SAT(S,G)) 3820 This timer is first set when the Origination(S,G) state machine 3821 transitions to the O state and is reset on the receipt of every 3822 data packet from S addressed to group G. When it expires, the 3823 Origination(S,G) state machine transitions to the NO state. This 3824 timer is normally set to SourceLifetime (see 4.8). 3826 +-------------+ Rcv Directly From S +-------------+ 3827 | |----------------------->| | 3828 |NotOriginator| | Originator | 3829 | |<-----------------------| | 3830 +-------------+ SAT Expires OR +-------------+ 3831 S NOT Direct Connect 3833 Figure 3: State Refresh State Machine 3835 In tabular form, the state machine is defined as follows: 3837 +----------------------------------------------------------------------+ 3838 | | Previous State | 3839 | +---------------+-------------------+ 3840 | Event | NotOriginator | Originator | 3841 +----------------------------------+---------------+-------------------+ 3842 | Receive Data from S AND | ->O | ->O Reset | 3843 | S directly connected | Set SRT(S,G) | SAT(S,G) | 3844 | | Set SAT(S,G) | | 3845 +----------------------------------+---------------+-------------------+ 3846 | SRT(S,G) Expires | N/A | ->O Send | 3847 | | | StateRefresh(S,G) | 3848 | | | Reset SRT(S,G) | 3849 +----------------------------------+---------------+-------------------+ 3850 | SAT(S,G) Expires | N/A | ->NO Cancel | 3851 | | | SRT(S,G) | 3852 +----------------------------------+---------------+-------------------+ 3853 | S no longer directly connected | ->NO | ->NO | 3854 | | | Cancel SRT(S,G) | 3855 | | | Cancel SAT(S,G) | 3856 +----------------------------------+---------------+-------------------+ 3857 4.5.2.1. Transitions from the NotOriginator (NO) State 3859 When the Originating(S,G) state machine is in the NotOriginator (NO) 3860 state, the following event may trigger a transition: 3862 Data Packet received from directly connected Source S addressed to 3863 group G 3864 The router MUST transition to an Originator (O) state, set SAT(S,G) 3865 to SourceLifetime, and set SRT(S,G) to StateRefreshInterval. The 3866 router SHOULD record the TTL of the packet for use in State Refresh 3867 messages. 3869 4.5.2.2. Transitions from the Originator (O) State 3871 When the Originating(S,G) state machine is in the Originator (O) state, 3872 the following events may trigger a transition: 3874 Receive Data Packet from S addressed to G 3875 The router remains in the Originator (O) state and MUST reset 3876 SAT(S,G) to SourceLifetime. The router SHOULD increase its recorded 3877 TTL to match the TTL of the packet, if the packet's TTL is larger 3878 than the previously recorded TTL. 3880 SRT(S,G) Expires 3881 The router remains in the Originator (O) state and MUST reset 3882 SRT(S,G) to StateRefreshInterval. The router MUST also generate 3883 State Refresh messages for transmission as described in the State 3884 Refresh Forwarding rules (section 4.5.1) except for the TTL. If the 3885 TTL of data packets from S to G are being recorded, then the TTL of 3886 each State Refresh message is set to the highest recorded TTL. 3887 Otherwise, the TTL is set to the configured State Refresh TTL. Let 3888 I denote the interface over which a State Refresh message is being 3889 sent. If the Prune(S,G) Downstream state machine for I is in the 3890 NoInfo (NI) state, then the Prune-Indicator bit MUST be set to 0 in 3891 the State Refresh message being sent over I. Otherwise the 3892 Prune-Indicator bit MUST be set to 1. 3894 SAT(S,G) Expires 3895 The router MUST cancel the SRT(S,G) timer and transition to the 3896 NotOriginator (NO) state. 3898 S is no longer directly connected 3899 The router MUST transition to the NotOriginator (NO) state and 3900 cancel both the SAT(S,G) and SRT(S,G). 3902 4.6. PIM Assert Messages 3904 4.6.1. Assert Metrics 3906 Assert metrics are defined as: 3908 struct assert_metric { 3909 metric_preference; 3910 route_metric; 3911 ip_address; 3912 }; 3914 When comparing assert_metrics, the metric_preference and route_metric 3915 field are compared in order, where the first lower value wins. If all 3916 fields are equal, the IP address of the router that sourced the Assert 3917 message is used as a tie-breaker, with the highest IP address winning. 3919 An Assert metric for (S,G) to include in (or compare against) an Assert 3920 message sent on interface I should be computed using the following 3921 pseudocode: 3923 assert_metric 3924 my_assert_metric(S,G,I) { 3925 if (CouldAssert(S,G,I) == TRUE) { 3926 return spt_assert_metric(S,G,I) 3927 } else { 3928 return infinite_assert_metric() 3929 } 3930 } 3932 spt_assert_metric(S,I) gives the Assert metric we use if we're sending 3933 an Assert based on active (S,G) forwarding state: 3935 assert_metric 3936 spt_assert_metric(S,I) { 3937 return {0,MRIB.pref(S),MRIB.metric(S),my_addr(I)} 3938 } 3940 MRIB.pref(X) and MRIB.metric(X) are the routing preference and routing 3941 metrics associated with the route to a particular (unicast) destination 3942 X, as determined by the MRIB. my_addr(I) is simply the router's network 3943 (e.g. IP) address that is associated with the local interface I. 3945 infinite_assert_metric() gives the Assert metric we need to send an 3946 Assert but doesn't match (S,G) forwarding state: 3948 assert_metric 3949 infinite_assert_metric() { 3950 return {1,infinity,infinity,0} 3951 } 3952 4.6.2. AssertCancel Messages 3954 An AssertCancel(S,G) message is simply an Assert message for (S,G) with 3955 infinite metric. The Assert winner sends such a message when it changes 3956 its upstream interface to this interface. Other routers will see this 3957 metric, causing those with forwarding state to send their own Asserts 3958 and re-establish an Assert winner. 3960 AssertCancel messages are simply an optimization. The original Assert 3961 timeout mechanism will allow a subnet to eventually become consistent; 3962 the AssertCancel mechanism simply causes faster convergence. No special 3963 processing is required for an AssertCancel message, since it is simply 3964 an Assert message from the current winner. 3966 4.6.3. Assert State Macros 3968 The macro lost_assert(S,G,I), is used in the olist computations of 3969 section 4.1.3, and is defined as follows: 3971 bool lost_assert(S,G,I) { 3972 if ( RPF_interface(S) == I ) { 3973 return FALSE 3974 } else { 3975 return (AssertWinner(S,G,I) != me AND 3976 (AssertWinnerMetric(S,G,I) is better than 3977 spt_assert_metric(S,G,I))) 3978 } 3979 } 3981 AssertWinner(S,G,I) defaults to NULL and AssertWinnerMetric(S,G,I) 3982 defaults to Infinity when in the NoInfo state. 3984 4.6.4. (S,G) Assert Message State Machine 3986 The (S,G) Assert state machine for interface I is shown in Figure 4. 3987 There are three states: 3989 NoInfo (NI) 3990 This router has no (S,G) Assert state on interface I. 3992 I am Assert Winner (W) 3993 This router has won an (S,G) Assert on interface I. It is now 3994 responsible for forwarding traffic from S destined for G via 3995 interface I. 3997 I am Assert Loser (L) 3998 This router has lost an (S,G) Assert on interface I. It must not 3999 forward packets from S destined for G onto interface I. 4001 In addition there is also an Assert Timer (AT(S,G,I)) that is used to 4002 time out Assert state. 4004 +-------------+ +-------------+ 4005 | | Rcv Pref Assert or SR | | 4006 | Winner |----------------------->| Loser | 4007 | | | | 4008 +-------------+ +-------------+ 4009 ^ | ^ | 4010 | | Rcv Pref Assert or| | 4011 | |AT Expires OR State Refresh| | 4012 | |CouldAssert->FALSE | | 4013 | | | | 4014 | | +-------------+ | | 4015 | +-------->| |----------+ | 4016 | | No Info | | 4017 +-------------| |<-------------+ 4018 Rcv Data from dnstrm +-------------+ Rcv Inf Assert from Win OR 4019 OR Rcv Inferior Assert Rcv Inf SR from Winner OR 4020 OR Rcv Inferior SR AT Expires OR 4021 CouldAssert Changes OR 4022 Winner's NLT Expires 4024 Figure 4: Assert State Machine 4026 In tabular form the state machine is defined as follows: 4028 +-------------------------------+--------------------------------------+ 4029 | | Previous State | 4030 | +------------+------------+------------+ 4031 | Event | No Info | Winner | Loser | 4032 +-------------------------------+------------+------------+------------+ 4033 | An (S,G) Data packet received | ->W Send | ->W Send | ->L | 4034 | on downstream interface | Assert(S,G)| Assert(S,G)| | 4035 | | Set | Set | | 4036 | | AT(S,G,I) | AT(S,G,I) | | 4037 +-------------------------------+--------------------------------------+ 4038 | Receive Inferior (Assert OR | N/A | N/A |->NI Cancel | 4039 | State Refresh) from Assert | | | AT(S,G,I) | 4040 | Winner | | | | 4041 +-------------------------------+--------------------------------------+ 4042 | Receive Inferior (Assert OR | ->W Send | ->W Send | ->L | 4043 | State Refresh) from non-Assert| Assert(S,G)| Assert(S,G)| | 4044 | Winner AND CouldAssert==TRUE | Set | Set | | 4045 | | AT(S,G,I) | AT(S,G,I) | | 4046 +-------------------------------+--------------------------------------+ 4047 +-------------------------------+--------------------------------------+ 4048 | | Previous State | 4049 | +------------+------------+------------+ 4050 | Event | No Info | Winner | Loser | 4051 +-------------------------------+------------+------------+------------+ 4052 | Receive Preferred Assert OR | ->L Send | ->L Send | ->L Set | 4053 | State Refresh | Prune(S,G) | Prune(S,G) | AT(S,G,I) | 4054 | | Set | Set | | 4055 | | AT(S,G,I) | AT(S,G,I) | | 4056 +-------------------------------+--------------------------------------+ 4057 | Send State Refresh | ->NI | ->W Reset | N/A | 4058 | | | AT(S,G,I) | | 4059 +-------------------------------+--------------------------------------+ 4060 | AT(S,G) Expires | N/A | ->NI | ->NI | 4061 +-------------------------------+--------------------------------------+ 4062 | CouldAssert -> FALSE | ->NI |->NI Cancel |->NI Cancel | 4063 | | | AT(S,G,I) | AT(S,G,I) | 4064 +-------------------------------+--------------------------------------+ 4065 | CouldAssert -> TRUE | ->NI | N/A |->NI Cancel | 4066 | | | | AT(S,G,I) | 4067 +-------------------------------+--------------------------------------+ 4068 | Winner's NLT(N,I) Expires | N/A | N/A |->NI Cancel | 4069 | | | | AT(S,G,I) | 4070 +-------------------------------+--------------------------------------+ 4071 | Receive Prune(S,G), Join(S,G) | ->NI | ->W | ->L Send | 4072 | or Graft(S,G) | | | Assert(S,G)| 4073 +-------------------------------+--------------------------------------+ 4075 Terminology: 4076 A "preferred assert" is one with a better metric than the current 4077 winner. An "inferior assert" is one with a worse metric than 4078 my_assert_metric(S,G,I). 4080 The state machine uses the following macro: 4082 CouldAssert(S,G,I) = (RPF_interface(S) != I) 4084 4.6.4.1. Transitions from NoInfo State 4086 When in NoInfo state, the following events may trigger transitions: 4088 An (S,G) data packet arrives on downstream interface I 4089 An (S,G) data packet arrived on a downstream interface. It is 4090 optimistically assumed that this router will be the Assert winner 4091 for this (S,G). The Assert state machine MUST transition to the "I 4092 am Assert Winner" state, send an Assert(S,G) to interface I, store 4093 its own address and metric as the Assert Winner and set the 4094 Assert_Timer (AT(S,G,I) to Assert_Time, thereby initiating the 4095 Assert negotiation for (S,G). 4097 Receive Inferior (Assert OR State Refresh) AND 4098 CouldAssert(S,G,I)==TRUE 4099 An Assert or State Refresh is received for (S,G) that is inferior 4100 to our own assert metric on interface I. The Assert state machine 4101 MUST transition to the "I am Assert Winner" state, send an 4102 Assert(S,G) to interface I, store its own address and metric as the 4103 Assert Winner and set the Assert Timer (AT(S,G,I)) to Assert_Time. 4105 Receive Preferred Assert or State Refresh 4106 The received Assert or State Refresh has a better metric than this 4107 router's and therefore the Assert state machine MUST transition to 4108 the "I am Assert Loser" state and store the Assert Winner's address 4109 and metric. If the metric was received in an Assert, the router MUST 4110 set the Assert Timer (AT(S,G,I)) to Assert_Time. If the metric was 4111 received in a State Refresh, the router MUST set the Assert Timer 4112 (AT(S,G,I)) to three times the received State Refresh Interval. If 4113 CouldAssert(S,G,I) == TRUE, the router MUST also multicast a 4114 Prune(S,G) to the Assert winner with a Prune Hold Time equal to the 4115 Assert Timer and evaluate any changes in its Upstream(S,G) state 4116 machine. 4118 4.6.4.2. Transitions from Winner State 4120 When in "I am Assert Winner" state, the following events trigger 4121 transitions: 4123 An (S,G) data packet arrives on downstream interface I 4124 An (S,G) data packet arrived on a downstream interface. The Assert 4125 state machine remains in the "I am Assert Winner" state. The router 4126 MUST send an Assert(S,G) to interface I and set the Assert Timer 4127 (AT(S,G,I) to Assert_Time. 4129 Receive Inferior Assert or State Refresh 4130 An (S,G) Assert is received containing a metric for S that is worse 4131 metric than this router's metric for S. Whoever sent the Assert is 4132 in error. The router MUST send an Assert(S,G) to interface I and 4133 reset the Assert Timer (AT(S,G,I)) to Assert_Time. 4135 Receive Preferred Assert or State Refresh 4136 An (S,G) Assert or State Refresh is received that has a better 4137 metric than this router's metric for S on interface I. The Assert 4138 state machine MUST transition to "I am Assert Loser" state and 4139 store the new Assert Winner's address and metric. If the metric was 4140 received in an Assert, the router MUST set the Assert Timer 4141 (AT(S,G,I)) to Assert_Time. If the metric was received in a State 4142 Refresh, the router MUST set the Assert Timer (AT(S,G,I)) to three 4143 times the State Refresh Interval. The router MUST also multicast a 4144 Prune(S,G) to the Assert winner with a Prune Hold Time equal to the 4145 Assert Timer and evaluate any changes in its Upstream(S,G) state 4146 machine. 4148 Send State Refresh 4149 The router is sending a State Refresh(S,G) message on interface I. 4150 The router MUST set the Assert Timer (AT(S,G,I)) to three times the 4151 State Refresh Interval contained in the State Refresh(S,G) message. 4153 AT(S,G,I) Expires 4154 The (S,G) Assert Timer (AT(S,G,I)) expires. The Assert state machine 4155 MUST transition to the NoInfo (NI) state. 4157 CouldAssert(S,G,I) -> FALSE 4158 This router's RPF interface changed so as to make CouldAssert(S,G,I) 4159 become false. This router can no longer perform the actions of the 4160 Assert winner, and so the Assert state machine MUST transition to 4161 NoInfo (NI) state, send an AssertCancel(S,G) to interface I, cancel 4162 the Assert Timer (AT(S,G,I)) and remove itself as the Assert Winner. 4164 4.6.4.3. Transitions from Loser State 4166 When in "I am Assert Loser" state, the following transitions can occur: 4168 Receive Inferior Assert or State Refresh from Current Winner 4169 An Assert or State Refresh is received from the current Assert 4170 winner that is worse than this router's metric for S (typically the 4171 winner's metric became worse). The Assert state machine MUST 4172 transition to NoInfo (NI) state and cancel AT(S,G,I). The router 4173 MUST delete the previous Assert Winner's address and metric and 4174 evaluate any possible transitions to its Upstream(S,G) state 4175 machine. Usually this router will eventually re-assert and win when 4176 data packets from S have started flowing again. 4178 Receive Preferred Assert or State Refresh 4179 An Assert or State Refresh is received that has a metric better than 4180 or equal to that of the current Assert winner. The Assert state 4181 machine remains in Loser (L) state. If the metric was received in 4182 an Assert, the router MUST set the Assert Timer (AT(S,G,I)) to 4183 Assert_Time. If the metric was received in a State Refresh, the 4184 router MUST set the Assert Timer (AT(S,G,I)) to three times the 4185 received State Refresh Interval. If the metric is better than the 4186 current Assert Winner, the router MUST store the address and metric 4187 of the new Assert Winner and if CouldAssert(S,G,I) == TRUE, the 4188 router MUST multicast a Prune(S,G) to the new Assert winner. 4190 AT(S,G,I) Expires 4191 The (S,G) Assert Timer (AT(S,G,I)) expires. The Assert state 4192 machine MUST transition to NoInfo (NI) state. The router MUST 4193 delete the Assert Winner's address and metric. If CouldAssert == 4194 TRUE, the router MUST evaluate any possible transitions to its 4195 Upstream(S,G) state machine. 4197 CouldAssert -> FALSE 4198 CouldAssert has become FALSE because interface I has become the RPF 4199 interface for S. The Assert state machine MUST transition to NoInfo 4200 (NI) state, cancel AT(S,G,I) and delete information concerning the 4201 Assert Winner on I. 4203 CouldAssert -> TRUE 4204 CouldAssert has become TRUE because interface I used to be the RPF 4205 interface for S, and now it is not. The Assert state machine MUST 4206 transition to NoInfo (NI) state, cancel AT(S,G,I) and delete 4207 information concerning the Assert Winner on I. 4209 Current Assert Winner's NeighborLiveness Timer Expires 4210 The current Assert winner's NeighborLiveness Timer (NLT(N,I)) has 4211 expired. The Assert state machine MUST transition to the NoInfo 4212 (NI) state, delete the Assert Winner's address and metric, and 4213 evaluate any possible transitions to its Upstream(S,G) state 4214 machine. 4216 Receive Prune(S,G), Join(S,G) or Graft(S,G) 4217 A Prune(S,G), Join(S,G) or Graft(S,G) message was received on 4218 interface I with its upstream neighbor address set to the router's 4219 address on I. The router MUST send an Assert(S,G) on the receiving 4220 interface I to initiate an Assert negotiation. The Assert state 4221 machine remains in the Assert Loser(L) state. If a Graft(S,G) was 4222 received, the router MUST respond with a GraftAck(S,G). 4224 4.6.5. Rationale for Assert Rules 4226 The following is a summary of the rules for generating and processing 4227 Assert messages. It is not intended to be definitive (the state 4228 machines and pseudocode provide the definitive behavior). Instead it 4229 provides some rationale for the behavior. 4231 1. The Assert winner for (S,G) must act as the local forwarder for (S,G) 4232 on behalf of all downstream members. 4233 2. PIM messages are directed towards to the RPF' neighbor and not to the 4234 regular RPF neighbor. 4235 3. An Assert loser that receives a Prune(S,G), Join(S,G) or Graft(S,G) 4236 directed to it initiates a new Assert negotiation so the downstream 4237 router can correct its RPF'(S). 4238 4. An Assert winner for (S,G) sends a cancelling assert when it is about 4239 to stop forwarding on an (S,G) entry. Example: if a router is being 4240 taken down, then a canceling assert is sent. 4242 4.7. PIM Packet Formats 4244 All PIM-DM packets use the same format as PIM-SM packets. In the event 4245 of a discrepancy, PIM-SM [4] should be considered the definitive 4246 specification. All PIM control messages have IP protocol number 103. 4247 All PIM-DM messages MUST be sent with a TTL of 1. All PIM-DM messages 4248 except Graft and Graft Ack messages MUST be sent to the ALL-PIM-ROUTERS 4249 group. Graft messages SHOULD be unicast to the RPF'(S). Graft Ack 4250 messages MUST be unicast to the sender of the Graft. 4252 The IPv4 ALL-PIM-ROUTERS group is 224.0.0.13. The IPv6 ALL-PIM-ROUTERS 4253 group is 'ff02::d'. 4255 4.7.1. PIM Header 4257 All PIM control messages have the following header: 4259 0 1 2 3 4260 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 4261 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4262 |PIM Ver| Type | Reserved | Checksum | 4263 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4265 PIM Ver 4266 PIM version number is 2. 4268 Type 4269 Types for specific PIM messages. Available types are: 4270 0 = Hello 4271 1 = Register (PIM-SM only) 4272 2 = Register Stop (PIM-SM only) 4273 3 = Join/Prune 4274 4 = Bootstrap (PIM-SM only) 4275 5 = Assert 4276 6 = Graft 4277 7 = Graft Ack 4278 8 = Candidate RP Advertisement (PIM-SM only) 4279 9 = State Refresh 4281 Reserved 4282 Set to zero on transmission. Ignored upon receipt. 4284 Checksum 4285 The checksum is standard IP checksum, i.e. the 16 bit one's complement 4286 of the one's complement sum of the entire PIM message. For computing 4287 checksum, the checksum field is zeroed. 4289 For IPv6, the checksum also includes the IPv6 "pseudo-header", as 4290 specified in RFC 2460, section 8.1 [13]. 4292 4.7.2. Encoded Unicast Address 4294 An Encoded Unicast Address has the following format: 4296 0 1 2 3 4297 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 4298 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4299 | Addr Family | Encoding Type | Unicast Address 4300 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+... 4302 Addr Family 4303 The PIM Address Family of the 'Unicast Address' field of this address. 4304 Values of 0-127 are as assigned by the IANA for Internet Address 4305 Families in [9]. Values 128-250 are reserved to be assigned by the 4306 IANA for PIM specific Address Families. Values 251-255 are designated 4307 for private use. As there is no assignment authority for this space, 4308 collisions should be expected. 4310 Encoding Type 4311 The type of encoding used with a specific Address Family. The value 4312 '0' is reserved for this field, and represents the native encoding of 4313 the Address Family 4315 Unicast Address 4316 The unicast address as represented by the given Address Family and 4317 Encoding Type. 4319 4.7.3. Encoded Group Address 4321 An Encoded Group address has the following format: 4323 0 1 2 3 4324 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 4325 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4326 | Addr Family | Encoding Type |B| Reserved |Z| Mask Len | 4327 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4328 | Group Multicast Address 4329 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+... 4331 Addr Family 4332 As described above. 4334 Encoding Type 4335 As described above. 4337 B 4338 Indicates the group range should use Bidirectional PIM [16]. 4339 Transmitted as zero, ignored upon receipt. 4341 Reserved 4342 Transmitted as zero. Ignored upon receipt. 4344 Z 4345 Indicates the group range is an admin scope zone. This is used in the 4346 Bootstrap Router Mechanism [18] only. For all other purposes, this bit 4347 is set to zero and ignored on receipt. 4349 Mask Len 4350 The mask length field is 8 bits. The value is the number of 4351 contiguous on bits left justified used as a mask, which combined with 4352 the address, describes a range of addresses. It is less than or equal 4353 to the address length in bits for the given Address Family and 4354 Encoding Type. If the message is sent for a single address then the 4355 mask length MUST equal the address length. PIM-DM routers MUST only 4356 send for a single address. 4358 Group Multicast Address 4359 The address of the multicast group. 4361 4.7.4. Encoded Source Address 4363 An Encoded Source address has the following format: 4365 0 1 2 3 4366 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 4367 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4368 | Addr Family | Encoding Type | Rsrvd |S|W|R| Mask Len | 4369 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4370 | Source Address 4371 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+... 4373 Addr Family 4374 As described above. 4376 Encoding Type 4377 As described above. 4379 Rsrvd 4380 Reserved. Transmitted as zero. Ignored upon receipt. 4382 S 4383 The Sparse Bit. Set to 0 for PIM-DM. Ignored upon receipt. 4385 W 4386 The Wild Card Bit. Set to 0 for PIM-DM. Ignored upon receipt. 4388 R 4389 The Rendezvous Point Tree bit. Set to 0 for PIM-DM. Ignored upon 4390 receipt. 4392 Mask Len 4393 As described above. PIM-DM routers MUST only send for a single 4394 source address. 4396 Source Address 4397 The source address. 4399 4.7.5. Hello Message Format 4401 The PIM Hello message, as defined by PIM-SM [4], has the following 4402 format: 4404 0 1 2 3 4405 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 4406 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4407 |PIM Ver| Type | Reserved | Checksum | 4408 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4409 | Option Type | Option Length | 4410 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4411 | Option Value | 4412 | ... | 4413 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4414 | . | 4415 | . | 4416 | . | 4417 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4418 | Option Type | Option Length | 4419 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4420 | Option Value | 4421 | ... | 4422 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4424 PIM Ver, Type, Reserved, Checksum 4425 Described above. 4427 Option Type 4428 The type of option given in the Option Value field. Available types 4429 are: 4430 0 Reserved 4431 1 Hello Hold Time 4432 2 LAN Prune Delay 4433 3-16 Reserved 4434 17 To be assigned by IANA 4435 18 Deprecated and SHOULD NOT be used 4436 19 DR Priority (PIM-SM Only) 4437 20 Generation ID 4438 21 State Refresh Capable 4439 22 Bidir Capable 4440 23-65000 To be assigned by IANA 4441 65001-65535 Reserved for Private Use [9] 4442 Unknown options SHOULD be ignored. 4444 4.7.5.1. Hello Hold Time Option 4446 0 1 2 3 4447 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 4448 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4449 | Type = 1 | Length = 2 | 4450 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4451 | Hold Time | 4452 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4454 Hold Time is the number of seconds a receiver MUST keep the neighbor 4455 reachable. If the Hold Time is set to '0xffff', the receiver of this 4456 message never times out the neighbor. This may be used with dial-on- 4457 demand links, to avoid keeping the link up with periodic Hello messages. 4458 Furthermore, if the Holdtime is set to '0', the information is timed out 4459 immediately. The Hello Hold Time option MUST be used by PIM-DM routers. 4461 4.7.5.2. LAN Prune Delay Option 4463 0 1 2 3 4464 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 4465 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4466 | Type = 2 | Length = 4 | 4467 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4468 |T| LAN Prune Delay | Override Interval | 4469 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4471 The LAN_Prune_Delay option is used to tune the prune propagation delay 4472 on multi-access LANs. The T bit is used by PIM-SM and SHOULD be set to 0 4473 by PIM-DM routers and ignored upon receipt. The LAN Delay and Override 4474 Interval fields are time intervals in units of milliseconds and are used 4475 to tune the value of the J/P Override Interval and its derived timer 4476 values. Section 4.3.5 describes how these values affect the behavior of 4477 a router. The LAN Prune Delay SHOULD be used by PIM-DM routers. 4479 4.7.5.3. Generation ID Option 4481 0 1 2 3 4482 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 4483 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4484 | Type = 20 | Length = 4 | 4485 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4486 | Generation ID | 4487 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4489 Generation ID is a random value for the interface on which the Hello 4490 message is sent. The Generation ID is regenerated whenever PIM 4491 forwarding is started or restarted on the interface. The Generation ID 4492 option MAY be used by PIM-DM routers. 4494 4.7.5.4. State Refresh Capable Option 4496 0 1 2 3 4497 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 4498 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4499 | Type = 21 | Length = 4 | 4500 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4501 | Version = 1 | Interval | Reserved | 4502 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4504 The Interval field is the router's configured State Refresh Interval in 4505 seconds. The Reserved field is set to zero and ignored upon reception. 4506 The State Refresh Capable option MUST be used by State Refresh capable 4507 PIM-DM routers. 4509 4.7.6. Join/Prune Message Format 4511 PIM Join/Prune messages, as defined in PIM-SM [4], have the following 4512 format: 4514 0 1 2 3 4515 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 4516 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4517 |PIM Ver| Type | Reserved | Checksum | 4518 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4519 | Upstream Neighbor Address (Encoded Unicast Format) | 4520 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4521 | Reserved | Num Groups | Hold Time | 4522 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4523 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4524 | Multicast Group Address 1 (Encoded Group Format) | 4525 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4526 | Number of Joined Sources | Number of Pruned Sources | 4527 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4528 | Joined Source Address 1 (Encoded Source Format) | 4529 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4530 | . | 4531 | . | 4532 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4533 | Joined Source Address n (Encoded Source Format) | 4534 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4535 | Pruned Source Address 1 (Encoded Source Format) | 4536 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4537 | . | 4538 | . | 4539 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4540 | Pruned Source Address n (Encoded Source Format) | 4541 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4542 | . | 4543 | . | 4544 | . | 4545 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4546 | Multicast Group Address m (Encoded Group Format) | 4547 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4548 | Number of Joined Sources | Number of Pruned Sources | 4549 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4550 | Joined Source Address 1 (Encoded Source Format) | 4551 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4552 | . | 4553 | . | 4554 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4555 | Joined Source Address n (Encoded Source Format) | 4556 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4557 | Pruned Source Address 1 (Encoded Source Format) | 4558 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4559 | . | 4560 | . | 4561 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4562 | Pruned Source Address n (Encoded Source Format) | 4563 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4565 PIM Ver, Type, Reserved, Checksum 4566 Described above. 4568 Upstream Neighbor Address 4569 The address of the upstream neighbor. The format for this address is 4570 given in the Encoded Unicast address in section 4.7.2. PIM-DM routers 4571 MUST set this field to the RPF next hop. 4573 Reserved 4574 Transmitted as zero. Ignored upon receipt. 4576 Hold Time 4577 The number of seconds a receiving PIM-DM router MUST keep a Prune 4578 state alive, unless removed by a Join or Graft message. If the Hold 4579 Time is '0xffff', the receiver MUST NOT remove the Prune state unless 4580 a corresponding Join or Graft message is received. The Hold Time is 4581 ignored in Join messages. 4583 Number of Groups 4584 Number of multicast group sets contained in the message. 4586 Multicast Group Address 4587 The multicast group address in the Encoded Multicast address format 4588 given in section 4.7.3. 4590 Number of Joined Sources 4591 Number of Join source addresses listed for a given group. 4593 Number of Pruned Sources 4594 Number of Prune source addresses listed for a given group. 4596 Join Source Address 1..n 4597 This list contains the sources from which the sending router wishes to 4598 continue to receive multicast messages for the given group on this 4599 interface. The addresses use the Encoded Source address format given 4600 in section 4.7.4. 4602 Prune Source Address 1..n 4603 This list contains the sources from which the sending router does not 4604 wish to receive multicast messages for the given group on this 4605 interface. The addresses use the Encoded Source address format given 4606 in section 4.7.4. 4608 4.7.7. Assert Message Format 4610 PIM Assert Messages, as defined in PIM-SM [4], have the following 4611 format: 4613 0 1 2 3 4614 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 4615 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4616 |PIM Ver| Type | Reserved | Checksum | 4617 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4618 | Multicast Group Address (Encoded Group Format) | 4619 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4620 | Source Address (Encoded Unicast Format) | 4621 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4622 |R| Metric Preference | 4623 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4624 | Metric | 4625 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4626 PIM Ver, Type, Reserved, Checksum 4627 Described above. 4629 Multicast Group Address 4630 The multicast group address in the Encoded Multicast address format 4631 given in section 4.7.3. 4633 Source Address 4634 The source address in the Encoded Unicast address format given in 4635 section 4.7.2. 4637 R 4638 The Rendezvous Point Tree bit. Set to 0 for PIM-DM. Ignored upon 4639 receipt. 4641 Metric Preference 4642 The preference value assigned to the unicast routing protocol that 4643 provided the route to the source. 4645 Metric 4646 The cost metric of the unicast route to the source. The metric is in 4647 units applicable to the unicast routing protocol used. 4649 4.7.8. Graft Message Format 4651 PIM Graft messages use the same format as Join/Prune messages except the 4652 Type field is set to 6. The source address MUST be in the Join section 4653 of the message. The Hold Time field SHOULD be zero and SHOULD be 4654 ignored when a Graft is received. 4656 4.7.9. Graft Ack Message Format 4658 PIM Graft Ack messages are identical in format to the received Graft 4659 message except the Type field is set to 7. The Upstream Neighbor 4660 Address field SHOULD be set to the sender of the Graft message and 4661 SHOULD be ignored upon receipt. 4663 4.7.10. State Refresh Message Format 4665 PIM State Refresh Messages have the following format: 4667 0 1 2 3 4668 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 4669 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4670 |PIM Ver| Type | Reserved | Checksum | 4671 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4672 | Multicast Group Address (Encoded Group Format) | 4673 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4674 | Source Address (Encoded Unicast Format) | 4675 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4676 | Originator Address (Encoded Unicast Format) | 4677 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4678 |R| Metric Preference | 4679 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4680 | Metric | 4681 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4682 | Masklen | TTL |P|N|O|Reserved | Interval | 4683 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4685 PIM Ver, Type, Reserved, Checksum 4686 Described above. 4688 Multicast Group Address 4689 The multicast group address in the Encoded Multicast address format 4690 given in section 4.7.3. 4692 Source Address 4693 The address of the data source in the Encoded Unicast address format 4694 given in section 4.7.2. 4696 Originator Address 4697 The address of the first hop router in the Encoded Unicast address 4698 format given in section 4.7.2. 4700 R 4701 The Rendezvous Point Tree bit. Set to 0 for PIM-DM. Ignored upon 4702 receipt. 4704 Metric Preference 4705 The preference value assigned to the unicast routing protocol that 4706 provided the route to the source. 4708 Metric 4709 The cost metric of the unicast route to the source. The metric is in 4710 units applicable to the unicast routing protocol used. 4712 Masklen 4713 The length of the address mask of the unicast route to the source. 4715 TTL 4716 Time To Live of the State Refresh message. Decremented each time the 4717 message is forwarded. Note that this is different from the IP Header 4718 TTL, which is always set to 1. 4720 P 4721 Prune indicator flag. This MUST be set to 1 if the State Refresh is 4722 to be sent on a Pruned interface. Otherwise, it MUST be set to 0. 4724 N 4725 Prune Now flag. This SHOULD be set to 1 by the State Refresh 4726 originator on every third State Refresh message and SHOULD be ignored 4727 upon receipt. This is for compatibility with earlier versions of 4728 state refresh. 4730 O 4731 Assert Override flag. This SHOULD be set to 1 by upstream routers on 4732 a LAN if the Assert Timer (AT(S,G)) is not running and SHOULD be 4733 ignored upon receipt. This is for compatibility with earlier versions 4734 of state refresh. 4736 Reserved 4737 Set to zero and ignored upon receipt. 4739 Interval 4740 Set by the originating router to the interval (in seconds) between 4741 consecutive State Refresh messages for this (S,G) pair. 4743 4.8. PIM-DM Timers 4745 PIM-DM maintains the following timers. All timers are countdown timers 4746 - they are set to a value and count down to zero, at which point they 4747 typically trigger an action. Of course they can just as easily be 4748 implemented as count-up timers, where the absolute expiry time is stored 4749 and compared against a real-time clock, but the language in this 4750 specification assumes that they count downwards towards zero. 4752 Global Timers 4753 Hello Timer: HT 4755 Per interface (I): 4756 Per neighbor (N): 4757 Neighbor Liveness Timer: NLT(N,I) 4759 Per (S,G) Pair: 4760 (S,G) Assert Timer: AT(S,G,I) 4761 (S,G) Prune Timer: PT(S,G,I) 4762 (S,G) PrunePending Timer: PPT(S,G,I) 4764 Per (S,G) Pair: 4765 (S,G) Graft Retry Timer: GRT(S,G) 4766 (S,G) Upstream Override Timer: OT(S,G) 4767 (S,G) Prune Limit Timer: PLT(S,G) 4768 (S,G) Source Active Timer: SAT(S,G) 4769 (S,G) State Refresh Timer: SRT(S,G) 4771 When timer values are started or restarted, they are set to default 4772 values. The following tables summarize those default values. 4774 Timer Name: Hello Timer (HT) 4775 +----------------------+--------+--------------------------------------+ 4776 | Value Name | Value | Explanation | 4777 +----------------------+--------+--------------------------------------+ 4778 |Hello_Period | 30 sec | Periodic interval for hello messages | 4779 +----------------------+--------+--------------------------------------+ 4780 |Triggered_Hello_Delay | 5 sec | Random interval for initial Hello | 4781 | | | message on bootup or triggered Hello | 4782 | | | message to a rebooting neighbor | 4783 +----------------------+--------+--------------------------------------+ 4785 Hello message are sent on every active interface once every Hello_Period 4786 seconds. At system power-up, the timer is initialized to 4787 rand(0,Triggered_Hello_Delay) to prevent synchronization. When a new or 4788 rebooting neighbor is detected, a responding Hello is sent within 4789 rand(0,Triggered_Hello_Delay). 4791 Timer Name: Neighbor Liveness Timer (NLT(N,I)) 4792 +-------------------+-----------------+--------------------------------+ 4793 | Value Name | Value | Explanation | 4794 +-------------------+-----------------+--------------------------------+ 4795 | Hello Holdtime | From message | Hold Time from Hello Message | 4796 +-------------------+-----------------+--------------------------------+ 4798 Timer Name: PrunePending Timer (PPT(S,G,I)) 4799 +-----------------------+---------------+------------------------------+ 4800 | Value Name | Value | Explanation | 4801 +-----------------------+---------------+------------------------------+ 4802 | J/P_Override_Interval | OI(I) + PD(I) | Short time after a Prune to | 4803 | | | allow other routers on the | 4804 | | | LAN to send a Join | 4805 +-----------------------+---------------+------------------------------+ 4807 The J/P_Override_Interval is the sum of the interface's 4808 Override_Interval (OI(I)) and Propagation_Delay (PD(I)). If all routers 4809 on a LAN are using the LAN Prune Delay option, both parameters MUST be 4810 set to the largest value on the LAN. Otherwise, the Override_Interval 4811 (OI(I)) MUST be set to 2.5 seconds and the Propagation_Delay (PD(I)) 4812 MUST be set to 0.5 seconds. 4814 Timer Name: Prune Timer (PT(S,G,I)) 4815 +----------------+----------------+------------------------------------+ 4816 | Value Name | Value | Explanation | 4817 +----------------+----------------+------------------------------------+ 4818 | Prune Holdtime | From message | Hold Time read from Prune Message | 4819 +----------------+----------------+------------------------------------+ 4821 Timer Name: Assert Timer (AT(S,G,I)) 4822 +--------------------------+---------+---------------------------------+ 4823 | Value Name | Value | Explanation | 4824 +--------------------------+---------+---------------------------------+ 4825 | Assert Time | 180 sec | Period after last assert before | 4826 | | | assert state is timed out | 4827 +--------------------------+---------+---------------------------------+ 4829 Note that for historical reasons, the Assert message lacks a Holdtime 4830 field. Thus changing the Assert Time from the default value is not 4831 recommended. If all members of a LAN are state refresh enabled, the 4832 Assert Time will be three times the received RefreshInterval(S,G). 4834 Timer Name: Graft Retry Timer (GRT(S,G)) 4835 +--------------------+-------+-----------------------------------------+ 4836 | Value Name | Value | Explanation | 4837 +--------------------+-------+-----------------------------------------+ 4838 | Graft_Retry_Period | 3 sec | In the absence of receipt of a GraftAck | 4839 | | | message, the time before retransmission | 4840 | | | of a Graft message | 4841 +--------------------+-------+-----------------------------------------+ 4843 Timer Name: Upstream Override Timer (OT(S,G)) 4844 +------------+----------------+----------------------------------------+ 4845 | Value Name | Value | Explanation | 4846 +------------+----------------+----------------------------------------| 4847 | t_override | rand(0, OI(I)) | Randomized delay to prevent response | 4848 | | | implosion when sending a join message | 4849 | | | to override someone else's prune | 4850 +------------+----------------+----------------------------------------+ 4852 t_override is a random value between 0 and the interface's 4853 Override_Interval (OI(I)). If all routers on a LAN are using the LAN 4854 Prune Delay option, the Override_Interval (OI(I)) MUST be set to the 4855 largest value on the LAN. Otherwise, the Override_Interval (OI(I)) MUST 4856 be set to 2.5 seconds. 4858 Timer Name: Prune Limit Timer (PLT(S,G)) 4859 +------------+--------------------+------------------------------------+ 4860 | Value Name | Value | Explanation | 4861 +------------+--------------------+------------------------------------| 4862 | t_limit | Equal to the Prune | Used to prevent Prune storms on a | 4863 | | Holdtime sent | LAN | 4864 +------------+--------------------+------------------------------------+ 4865 Timer Name: Source Active Timer (SAT(S,G)) 4866 +----------------+-------------------+---------------------------------+ 4867 | Value Name | Value | Explanation | 4868 +----------------+-------------------+---------------------------------+ 4869 | SourceLifetime | Default: 210 secs | Period of time after receiving | 4870 | | | a multicast message a directly | 4871 | | | attached router will continue | 4872 | | | to send State Refresh messages | 4873 +----------------+-------------------+---------------------------------+ 4875 Timer Name: State Refresh Timer (SRT(S,G)) 4876 +-----------------+------------------+---------------------------------+ 4877 | Value Name | Value | Explanation | 4878 +-----------------+------------------+---------------------------------+ 4879 | RefreshInterval | Default: 60 secs | Interval between successive | 4880 | | | state refresh messages | 4881 +-----------------+------------------+---------------------------------+ 4883 5. Protocol Interaction Considerations 4885 PIM-DM is designed to be independent of underlying unicast routing 4886 protocols and will interact only to the extent needed to perform RPF 4887 checks. It is generally assumed that multicast area and autonomous 4888 system boundaries will correspond to the same boundaries for unicast 4889 routing, though a deployment which does not follow this assumption is 4890 not precluded by this specification. 4892 In general, PIM-DM interactions with other multicast routing protocols 4893 should be in compliance with RFC 2715 [7]. Other specific 4894 interactions are noted below. 4896 5.1. PIM-SM Interactions 4898 PIM-DM is not intended to interact directly with PIM-SM, even though 4899 they share a common packet format. It is particularly important to note 4900 that a router cannot differentiate between a PIM-DM neighbor and a 4901 PIM-SM neighbor based on Hello messages. 4903 In the event that a PIM-DM router becomes a neighbor of a PIM-SM router 4904 they will effectively form a simplex link with the PIM-DM router sending 4905 all multicast messages to the PIM-SM router while the PIM-SM router 4906 sends no multicast messages to the PIM-DM router. 4908 The common packet format permits a hybrid PIM-SM/DM implementation that 4909 would use PIM-SM when a rendezvous point is known and PIM-DM when one is 4910 not. Such an implementation is outside the scope of this document. 4912 5.2. IGMP Interactions 4914 PIM-DM will forward received multicast data packets to neighboring host 4915 group members in all cases except when the PIM-DM router is in an Assert 4916 Loser state on that interface. Note that a PIM Prune message is not 4917 permitted to prevent the delivery of messages to a network with group 4918 members. 4920 A PIM-DM Router MAY use the DR Priority option described in PIM-SM [13] 4921 to elect an IGMP v1 querier. 4923 5.3. Source Specific Multicast (SSM) Interactions 4925 PIM-DM makes no special considerations for SSM [14]. All Prunes and 4926 Grafts within the protocol are for a specific source, so no additional 4927 checks need be made. 4929 5.4. Multicast Group Scope Boundary Interactions 4931 While multicast group scope boundaries are generally identical to 4932 routing area boundaries, it is conceivable that a routing area might be 4933 partitioned for a particular multicast group. PIM-DM routers MUST NOT 4934 send any messages concerning a particular group across that group's 4935 scope boundary. 4937 6. IANA Considerations 4939 6.1. PIM Address Family 4941 The PIM Address Family field was chosen to be 8 bits as a tradeoff 4942 between packet format and use of the IANA assigned numbers. When the 4943 PIM packet format was designed, only 15 values were assigned for Address 4944 Families and large numbers of new Address Families were not envisioned, 4945 8 bits seemed large enough. However, the IANA assigns Address Families 4946 in a 16 bit value. Therefore, the PIM Address Family is allocated as 4947 follows: 4949 Values 0 through 127 are designated to have the same meaning as IANA 4950 assigned Address Family Numbers [9]. 4952 Values 128 through 250 are designated to be assigned by the IANA based 4953 upon IESG approval as defined in [8]. 4955 Values 251 through 255 are designated for Private Use, as defined in 4956 [8]. 4958 6.2. PIM Hello Options 4960 Values 17 through 65000 are to be assigned by the IANA. Since the space 4961 is large, they may be assigned as First Come First Served as defined in 4962 [8]. Such assignments are valid for one year, and may be renewed. 4963 Permanent assignments require a specification as defined in [8]. 4965 7. Security Considerations 4967 The IPsec authentication header [10] MAY be used to provide data 4968 integrity protection and groupwise data origin authentication of PIM 4969 protocol messages. Authentication of PIM messages can protect against 4970 unwanted behaviors caused by unauthorized or altered PIM messages. In 4971 any case, a PIM router SHOULD NOT accept and process PIM messages from 4972 neighbors unless a valid Hello message has been received from that 4973 neighbor. 4975 We should note that PIM-DM has no rendezvous point, and therefore no 4976 single point of failure that may be vulnerable. It is further worth 4977 noting that because PIM-DM uses unicast routes provided by an unknown 4978 routing protocol, it may suffer collateral effects if the unicast 4979 routing protocol is attacked. 4981 7.1. Attacks Based on Forged Messages 4983 The extent of possible damage depends on the type of counterfeit 4984 messages accepted. We next consider the impact of possible forgeries. A 4985 forged PIM-DM message is link local, and can only reach a LAN if it was 4986 sent by a local host or if it was allowed onto the LAN by a compromised 4987 or non-compliant router. 4989 1. A forged a Hello message can cause multicast traffic to be delivered 4990 to links where there are no legitimate requestors, potentially 4991 wasting bandwidth on that link. On a multi-access LAN, the effects 4992 are limited without the capability to forge a Join message since 4993 other routers will Prune the link if the traffic is not desired. 4995 2. A forged Join/Prune message can cause multicast traffic to be 4996 delivered to links where there are no legitimate requestors, 4997 potentially wasting bandwidth on that link. A forged Prune message 4998 on a multi-access LAN is generally not a significant attack in PIM, 4999 because any legitimately joined router on the LAN would override the 5000 Prune with a Join before the upstream router stops forwarding data 5001 to the LAN. 5003 3. A forged Graft message can cause multicast traffic to be delivered to 5004 links where there are no legitimate requestors, potentially wasting 5005 bandwidth on that link. In principle, Graft messages could be sent 5006 multiple hops since they are unicast to the upstream router. This 5007 should not be a problem since the remote forger should have no way 5008 to get a Hello message to the target of the attack. Without a valid 5009 Hello message, the receiving router SHOULD NOT accept the Graft. 5011 4. A forged GraftAck message has no impact since it will be ignored 5012 unless the router has recently sent a Graft to its upstream router. 5014 5. By forging an Assert message on a multi-access LAN, an attacker could 5015 cause the legitimate forwarder to stop forwarding traffic to the LAN. 5016 Such a forgery would prevent any hosts downstream of that LAN from 5017 receiving traffic. 5019 6. A forged State Refresh message on a multi-access LAN would have the 5020 same impact as a forged Assert message, having the same general 5021 functions. In addition, forged State Refresh messages would be 5022 propagated downstream and might be used in a denial of service 5023 attack. Therefore, a PIM-DM router SHOULD rate limit State Refresh 5024 messages propagated. 5026 7.2. Non-cryptographic Authentication Mechanisms 5028 A PIM-DM router SHOULD provide an option to limit the set of neighbors 5029 from which it will accept PIM-DM messages. Either static configuration 5030 of IP addresses or an IPSec security association may be used. All 5031 options that restrict the range of addresses from which packets are 5032 accepted MUST default to allowing all packets. 5034 Furthermore, a PIM router SHOULD NOT accept protocol messages from a 5035 router from which it has not yet received a valid Hello message. 5037 7.3. Authentication Using IPsec 5039 The IPSec [10] transport mode using the Authentication Header (AH) is 5040 the recommended method to prevent the above attacks in PIM. The 5041 specific AH authentication algorithm and parameters, including the 5042 choice of authentication algorithm and the choice of key, are configure 5043 by the network administrator. The Encapsulating Security Payload (ESP) 5044 MAY also be used to provide both encryption and authentication of PIM 5045 protocol messages. When IPsec authentication is used, a PIM router 5046 SHOULD reject (drop without processing) any unauthorized PIM protocol 5047 messages. 5049 To use IPSec, the administrator of a PIM network configures each PIM 5050 router with one or more Security Associations and associated Security 5051 Parameters Indices that are used by senders to sign PIM protocol 5052 messages and are used by receivers to authenticate received PIM protocol 5053 messages. This document does not describe protocols for establishing 5054 Security Associations. It assumes that manual configuration of Security 5055 Associations is performed, but it does not preclude the use of some 5056 future negotiation protocol such as GDOI [17] to establish Security 5057 Associations. 5059 The network administrator defines a Security Association (SA) and 5060 Security Parameters Index (SPI) that is to be used to authenticate all 5061 PIM-DM protocol messages from each router on each link in a PIM-DM 5062 domain. 5064 In order to avoid the problem of allocating individual keys for each 5065 neighbor on a link to each individual router, it is acceptable to 5066 establish only one authentication key for all PIM-DM routers on a link. 5067 This will not specifically authenticate the individual router sending 5068 the message, but will assure that the sender is a PIM-DM router on that 5069 link. If this method is used, the receiver of the message MUST ignore 5070 the received sequence number, thus disabling anti-replay mechanisms. 5071 The effects of disabling anti-replay mechanisms are essentially the same 5072 as the effects of forged messages described in section 7.1 with the 5073 additional protection that the forger can only reuse legitimate 5074 messages. 5076 The Security Policy Database at a PIM-DM router should be configured to 5077 ensure that all incoming and outgoing PIM-DM packets use the SA 5078 associated with the interface to which the packet is sent. Note that, 5079 according to [10], there is nominally a different Security Association 5080 Database (SAD) for each router interface. Thus, the selected Security 5081 Association for an inbound PIM-DM packet can vary depending on the 5082 interface on which the packet arrived. This fact allows the network 5083 administrator to use different authentication methods for each link, 5084 even though the destination address is the same for most PIM-DM packets, 5085 regardless of interface. 5087 7.4. Denial of Service Attacks 5089 There are a number of possible denial of service attacks against PIM 5090 that can be caused by generating false PIM protocol messages or even by 5091 generating false data traffic. Authenticating PIM protocol traffic 5092 prevents some, but not all of these attacks. The possible attacks 5093 include: 5095 * Sending packets to many different group addresses quickly can be a 5096 denial of service attack in and of itself. These messages will 5097 initially be flooded throughout the network before they are pruned 5098 back. The maintenance of state machines and State Refresh messages 5099 will be a continual drain on network resources. 5101 * Forged State Refresh messages sent quickly could be propagated by 5102 downstream routers, creating a potential denial of service attack. 5103 Therefore, a PIM-DM router SHOULD rate limit State Refresh messages 5104 propagated. 5106 8. Authors' Addresses 5108 Andrew Adams 5109 NextHop Technologies 5110 825 Victors Way, Suite 100 5111 Ann Arbor, MI 48108-2738 5112 ala@nexthop.com 5114 Jonathan Nicholas 5115 ITT Industries 5116 Aerospace/Communications Division 5117 100 Kingsland Rd 5118 Clifton, NJ 07014 5119 jonathan.nicholas@itt.com 5121 William Siadak 5122 NextHop Technologies 5123 825 Victors Way, Suite 100 5124 Ann Arbor, MI 48108-2738 5125 wfs@nexthop.com 5127 9. Acknowledgments 5129 The major features of PIM-DM were originally designed by Stephen 5130 Deering, Deborah Estrin, Dino Farinacci, Van Jacobson, Ahmed Helmy, 5131 David Meyer, and Liming Wei. Additional features for state refresh 5132 were designed by Dino Farinacci, Isidor Kouvelas and Kurt Windisch. 5133 This revision was undertaken to incorporate some of the lessons learned 5134 during the evolution of the PIM-SM specification and early deployments 5135 of PIM-DM. 5137 Thanks the PIM Working Group for their comments. 5139 10. References 5141 10.1 Normative References 5143 [1] S.E. Deering, "Host Extensions for IP Multicasting", March 1989, 5144 RFC 1112. 5146 [2] W.Fenner, "Internet Group Management Protocol, Version 2", 5147 November 1997, RFC 2236. 5149 [3] B. Cain, S. Deering, B. Fenner, I. Kouvelas, A. Thyagarajan, 5150 "Internet Group Management Protocol, Version 3", 5151 October 2002, RFC 3376. 5153 [4] D. Estrin, D. Farinacci, A. Helmy, D. Thaler, S. Deering, 5154 M. Handley, V. Jacobson, C. Liu, P. Sharma, L. Wei, "Protocol 5155 Independent Multicast-Sparse Mode (PIM-SM): Protocol 5156 Specification", June 1998, RFC 2362. 5158 [5] S. Deering, R. Hinden, "Internet Protocol, Version 6 (IPv6) 5159 Specification", December 1998, RFC 2460. 5161 [6] S. Deering, W. Fenner, B. Haberman, "Multicast Listener Discovery 5162 (MLD) for IPv6", October 1999, RFC 2710. 5164 [7] D. Thaler, "Interoperability Rules for Multicast Routing 5165 Protocols", October 1999, RFC 2715. 5167 [8] T. Narten, H. Alvestrand, "Guidelines for Writing an IANA 5168 Considerations Section in RFCs", October 1998, RFC 2434. 5170 [9] IANA, "Address Family Numbers", linked from 5171 http://www.iana.org/numbers.html. 5173 [10] S. Kent, R. Atkinson, "Security Architecture for the Internet 5174 Protocol", November 1998, RFC 2401. 5176 10.2 Informative References 5178 [11] S.E. Deering, "Multicast Routing in a Datagram Internetwork", 5179 Ph.D. Thesis, Electrical Engineering Dept., Stanford University, 5180 December 1991. 5182 [12] D. Waitzman, B.Partridge, S.Deering, "Distance Vector Multicast 5183 Routing Protocol", November 1988, RFC 1075 5185 [13] W. Fenner, M. Handley, H.Holbrook, I. Kouvelas, "Protocol 5186 Independent Multicast - Sparse Mode (PIM-SM): Protocol 5187 Specification (Revised)", draft-ietf-pim-sm-v2-new-09.txt, 5188 work in progress. 5190 [14] H.Holbrook, B. Cain, "Source Specific Multicast for IP", 5191 draft-ietf-ssm-arch-04.txt, work in progress. 5193 [15] K.McCloghrie, D.Farinacci, D.Thaler, B.Fenner, "Protocol 5194 Independent Multicast MIB for IPv4", October 2000, RFC 2934 5196 [16] M. Handley, I. Kouvelas, T. Speakman, L. Vicisano, "Bi-directional 5197 Protocol Independent Multicast", draft-ietf-pim-bidir-06.txt, 5198 work in progress. 5200 [17] M. Baugher, B. Weis, T. Hardjono, H. Harney, "The Group Domain of 5201 Interpretation", July 2003, RFC 3547. 5203 [18] W. Fenner, M. Handley, R. Kermode, D. Thaler, "Bootstrap Router 5204 (BSR) Mechanism for PIM Sparse Mode", draft-ietf-pim-sm-bsr-03.txt, 5205 work in progress. 5207 11. Full Copyright Statement 5209 Copyright (C) The Internet Society (2004). All Rights Reserved. 5211 This document and translations of it may be copied and furnished to 5212 others, and derivative works that comment on or otherwise explain it 5213 or assist in its implementation may be prepared, copied, published and 5214 distributed, in whole or in part, without restriction of any kind, 5215 provided that the above copyright notice and this paragraph are 5216 included on all such copies and derivative works. However, this 5217 document itself may not be modified in any way, such as by removing 5218 the copyright notice or references to the Internet Society or other 5219 internet organizations, except as needed for the purpose of 5220 developing Internet standards in which case the procedures for 5221 copyrights defined in the Internet Standards process must be 5222 followed, or as required to translate it into languages other than 5223 English. 5225 The limited permissions granted above are perpetual and will not be 5226 revoked by the Internet Society or its successors or assigns. 5228 This document and the information contained herein is provided on an 5229 "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING 5230 TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING 5231 BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION 5232 HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF 5233 MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.