idnits 2.17.00 (12 Aug 2021) /tmp/idnits10919/draft-ietf-idmr-pim-sm-specv2-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Cannot find the required boilerplate sections (Copyright, IPR, etc.) in this document. Expected boilerplate is as follows today (2022-05-14) according to https://trustee.ietf.org/license-info : IETF Trust Legal Provisions of 28-dec-2009, Section 6.a: This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 2: Copyright (c) 2022 IETF Trust and the persons identified as the document authors. All rights reserved. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 3: This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** Missing expiration date. The document expiration date should appear on the first and last page. ** 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. ** Expected the document's filename to be given on the first page, but didn't find any ** The document is more than 15 pages and seems to lack a Table of Contents. == No 'Intended status' indicated for this document; assuming Proposed Standard == The page length should not exceed 58 lines per page, but there was 74 longer pages, the longest (page 1) being 67 lines == It seems as if not all pages are separated by form feeds - found 0 form feeds but 80 pages Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an Abstract section. ** The document seems to lack a Security Considerations section. (A line matching the expected section header was found, but with an unexpected indentation: ' 3.10 Security' ) ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** The document seems to lack an Authors' Addresses Section. ** There are 1106 instances of weird spacing in the document. Is it really formatted ragged-right, rather than justified? ** There are 6 instances of too long lines in the document, the longest one being 6 characters in excess of 72. ** There are 2242 instances of lines with control characters in the document. == There are 4 instances of lines with non-RFC6890-compliant IPv4 addresses in the document. If these are example addresses, they should be changed. == There are 5 instances of lines with multicast IPv4 addresses in the document. If these are generic example addresses, they should be changed to use the 233.252.0.x range defined in RFC 5771 Miscellaneous warnings: ---------------------------------------------------------------------------- == Line 17 has weird spacing: '... Drafts are ...' == Line 18 has weird spacing: '...cuments of t...' == Line 19 has weird spacing: '...ay also distr...' == Line 23 has weird spacing: '... Drafts may ...' == Line 24 has weird spacing: '...iate to use I...' == (1101 more instances...) == Couldn't figure out when the document was first submitted -- there may comments or warnings related to the use of a disclaimer for pre-RFC5378 work that could not be issued because of this. Please check the Legal Provisions document at https://trustee.ietf.org/license-info to determine if you need the pre-RFC5378 disclaimer. -- Couldn't find a document date in the document -- date freshness check skipped. Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) -- Missing reference section? '1' on line 49 looks like a reference -- Missing reference section? '2' on line 49 looks like a reference -- Missing reference section? '3' on line 65 looks like a reference -- Missing reference section? '4' on line 114 looks like a reference -- Missing reference section? '5' on line 114 looks like a reference -- Missing reference section? '6' on line 1933 looks like a reference -- Missing reference section? 'Hello-Period' on line 1885 looks like a reference -- Missing reference section? 'Hello-Holdtime' on line 1882 looks like a reference -- Missing reference section? 'Register-Suppression-Timeout' on line 1861 looks like a reference -- Missing reference section? 'Probe-Time' on line 1863 looks like a reference -- Missing reference section? 'Bootstrap-Timeout' on line 2813 looks like a reference -- Missing reference section? '7' on line 1592 looks like a reference -- Missing reference section? 'Data-Timeout' on line 1850 looks like a reference -- Missing reference section? 'Assert-Timeout' on line 1870 looks like a reference -- Missing reference section? 'Random-Delay-Join-Timeout' on line 1874 looks like a reference -- Missing reference section? 'Hello-Timer' on line 1746 looks like a reference -- Missing reference section? 'C-RP-Adv-Period' on line 1892 looks like a reference -- Missing reference section? 'RP-Holdtime' on line 1890 looks like a reference -- Missing reference section? 'Bootstrap-Timer' on line 1785 looks like a reference -- Missing reference section? 'Bootstrap-Period' on line 2764 looks like a reference -- Missing reference section? '8' on line 2603 looks like a reference -- Missing reference section? 'Aug 96' on line 2691 looks like a reference Summary: 15 errors (**), 0 flaws (~~), 12 warnings (==), 23 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group Deborah Estrin (USC) 3 Internet Draft Dino Farinacci (CISCO) 4 Ahmed Helmy (USC) 5 David Thaler (UMICH) 6 Steven Deering (XEROX) 7 Mark Handley (UCL) 8 Van Jacobson (LBL) 9 Chinggung Liu (USC) 10 Puneet Sharma (USC) 11 Liming Wei (CISCO) * 12 Protocol Independent Multicast-Sparse Mode (PIM-SM): Protocol 13 Specification 15 Status of This Memo 17 This document is an Internet Draft. Internet Drafts are working 18 documents of the Internet Engineering Task Force (IETF), its Areas, 19 and its Working Groups. (Note that other groups may also distribute 20 working documents as Internet Drafts). 22 Internet Drafts are draft documents valid for a maximum of six 23 months. Internet Drafts may be updated, replaced, or obsoleted by 24 other documents at any time. It is not appropriate to use Internet 25 Drafts as reference material or to cite them other than as a 26 ``working'' draft'' or ``work in progress.'' 28 Please check the I-D abstract listing contained in each Internet 29 Draft directory to learn the current status of this or any other 30 Internet Draft. 32 [*] The author list has been reordered to reflect the involvement in 33 detailed editorial work on this specification document. 34 The first four authors are the primary editors and are listed 35 alphabetically. 36 The rest of the authors, also listed alphabetically, participated 37 in all aspects of the architectural and detailed design but 38 managed to get away without hacking the latex! 40 1 Introduction 42 This document describes a protocol for efficiently routing to 43 multicast groups that may span wide-area (and inter-domain) 44 internets. We refer to the approach as Protocol Independent 45 Multicast--Sparse Mode (PIM-SM) because it is not dependent on any 46 particular unicast routing protocol, and because it is designed to 47 support sparse groups as defined in [1][2]. This document describes 48 the protocol details. For the motivation behind the design and a 49 description of the architecture, see [1][2]. Section 2 summarizes 50 PIM-SM operation. It describes the protocol from a network 51 perspective, in particular, how the participating routers interact to 52 create and maintain the multicast distribution tree. Section 3 53 describes PIM-SM operations from the perspective of a single router 54 implementing the protocol; this section constitutes the main body of 55 the protocol specification. It is organized according to PIM-SM 56 message type; for each message type we describe its contents, its 57 generation, and its processing. 59 Sections 3.8 and 3.9 summarize the timers and flags referred to 60 throughout this document. Section 4 provides packet format details. 62 The most significant functional changes since the January '95 version 63 involve the Rendezvous Point-related mechanisms, several resulting 64 simplifications to the protocol, and removal of the PIM-DM protocol 65 details to a separate document [3] (for clarity). 67 2 PIM-SM Protocol Overview 69 In this section we provide an overview of the architectural 70 components of PIM-SM. 72 A router receives explicit Join/Prune messages from those neighboring 73 routers that have downstream group members. The router then forwards 74 data packets addressed to a multicast group, G, only onto those 75 interfaces on which explicit joins have been received. Note that all 76 routers mentioned in this document are assumed to be PIM-SM capable, 77 unless otherwise specified. 79 A Designated Router (DR) sends periodic Join/Prune messages toward a 80 group-specific Rendezvous Point (RP) for each group for which it has 81 active members. Each router along the path toward the RP builds a 82 wildcard (any-source) state for the group and sends Join/Prune 83 messages on toward the RP. We use the term route entry to refer to 84 the state maintained in a router to represent the distribution tree. 85 A route entry may include such fields as the source address, the 86 group address, the incoming interface from which packets are 87 accepted, the list of outgoing interfaces to which packets are sent, 88 timers, flag bits, etc. The wildcard route entry's incoming interface 89 points toward the RP; the outgoing interfaces point to the 90 neighboring downstream routers that have sent Join/Prune messages 91 toward the RP. This state creates a shared, RP-centered, distribution 92 tree that reaches all group members. When a data source first sends 93 to a group, its DR unicasts Register messages to the RP with the 94 source's data packets encapsulated within. If the data rate is high, 95 the RP can send source-specific Join/Prune messages back towards the 96 source and the source's data packets will follow the resulting 97 forwarding state and travel unencapsulated to the RP. Whether they 98 arrive encapsulated or natively, the RP forwards the source's 99 decapsulated data packets down the RP-centered distribution tree 100 toward group members. If the data rate warrants it, routers with 101 local receivers can join a source-specific, shortest path, 102 distribution tree, and prune this source's packets off of the shared 103 RP-centered tree. For low data rate sources, neither the RP, nor 104 last-hop routers need join a source-specific shortest path tree and 105 data packets can be delivered via the shared, RP-tree. 107 The following subsections describe SM operation in more detail, in 108 particular, the control messages, and the actions they trigger. 110 2.1 Local hosts joining a group 112 In order to join a multicast group, G, a host conveys its membership 113 information through the Internet Group Management Protocol (IGMP), as 114 specified in [4][5], (see figure 1). From this point on we refer to 115 such a host as a receiver, R, (or member) of the group G. 117 Note that all figures used in this section are for illustration and 118 are not intended to be complete. For complete and detailed protocol 119 action see Section 3. 121 [Figures are present only in the postscript version] 122 Fig. 1 Example: how a receiver joins, and sets up shared tree 124 When a DR (e.g., router A in figure 1) gets a membership indication 125 from IGMP for a new group, G, the DR looks up the associated RP. The 126 DR creates a wildcard multicast route entry for the group, referred 127 to here as a (*,G) entry; if there is no more specific match for a 128 particular source, the packet will be forwarded according to this 129 entry. 131 The RP address is included in a special field in the route entry and 132 is included in periodic upstream Join/Prune messages. The outgoing 133 interface is set to that included in the IGMP membership indication 134 for the new member. The incoming interface is set to the interface 135 used to send unicast packets to the RP. 137 When there are no longer directly connected members for the group, 138 IGMP notifies the DR. If the DR has neither local members nor 139 downstream receivers, the (*,G) state is deleted. 141 2.2 Establishing the RP-rooted shared tree 143 Triggered by the (*,G) state, the DR creates a Join/Prune message 144 with the RP address in its join list and the the wildcard bit (WC- 145 bit) and RP-tree bit (RPT-bit) set to 1. The WC-bit indicates that 146 any source may match and be forwarded according to this entry if 147 there is no longer match; the RPT-bit indicates that this join is 148 being sent up the shared, RP-tree. The prune list is left empty. When 149 the RPT-bit is set to 1 it indicates that the join is associated with 150 the shared RP-tree and therefore the Join/Prune message is propagated 151 along the RP-tree. When the WC-bit is set to 1 it indicates that the 152 address is an RP and the downstream receivers expect to receive 153 packets from all sources via this (shared tree) path. The term RPT- 154 bit is used to refer to both the RPT-bit flags associated with route 155 entries, and the RPT-bit included in each encoded address in a 156 Join/Prune message. 158 Each upstream router creates or updates its multicast route entry for 159 (*,G) when it receives a Join/Prune with the RPT-bit and WC-bit set. 160 The interface on which the Join/Prune message arrived is added to the 161 list of outgoing interfaces (oifs) for (*,G). Based on this entry 162 each upstream router between the receiver and the RP sends a 163 Join/Prune message in which the join list includes the RP. The packet 164 payload contains Multicast-Address=G, Join=RP,WC-bit,RPT-bit, 165 Prune=NULL. 167 2.3 Hosts sending to a group 169 When a host starts sending multicast data packets to a group, 170 initially its DR must deliver each packet to the RP for distribution 171 down the RP-tree (see figure 2). The sender's DR initially 172 encapsulates each data packet in a Register message and unicasts it 173 to the RP for that group. The RP decapsulates each Register message 174 and forwards the enclosed data packet natively to downstream members 175 on the shared RP-tree. 177 [Figures are present only in the postscript version] 178 Fig. 2 Example: a host sending to a group 180 If the data rate of the source warrants the use of a source-specific 181 shortest path tree (SPT), the RP may construct a new multicast route 182 entry that is specific to the source, hereafter referred to as (S,G) 183 state, and send periodic Join/Prune messages toward the source. Note 184 that over time, the rules for when to switch can be modified without 185 global coordination. When and if the RP does switch to the SPT, the 186 routers between the source and the RP build and maintain (S,G) state 187 in response to these messages and send (S,G) messages upstream toward 188 the source. 190 The source's DR must stop encapsulating data packets in Registers 191 when (and so long as) it receives Register-Stop messages from the RP. 192 The RP triggers Register-Stop messages in response to Registers, if 193 the RP has no downstream receivers for the group (or for that 194 particular source), or if the RP has already joined the (S,G) tree 195 and is receiving the data packets natively. Each source's DR 196 maintains, per (S,G), a Register-Suppression-timer. The Register- 197 Suppression-timer is started by the Register-Stop message; upon 198 expiration, the source's DR resumes sending data packets to the RP, 199 encapsulated in Register messages. 201 2.4 Switching from shared tree (RP-tree) to shortest path tree (SP- 202 tree)} 204 A router with directly-connected members first joins the shared RP- 205 tree. The router can switch to a source's shortest path tree (SP- 206 tree) after receiving packets from that source over the shared RP- 207 tree. The recommended policy is to initiate the switch to the SP-tree 208 after receiving a significant number of data packets during a 209 specified time interval from a particular source. To realize this 210 policy the router can monitor data packets from sources for which it 211 has no source-specific multicast route entry and initiate such an 212 entry when the data rate exceeds the configured threshold. As shown 213 in figure 3, router `A' initiates a (S,G) state. 215 [Figures are present only in the postscript version] 216 Fig. 3 Example: Switching from shared tree to shortest path tree 218 When a (S,G) entry is activated (and periodically so long as the 219 state exists), a Join/Prune message is sent upstream towards the 220 source, S, with S in the join list. The payload contains Multicast- 221 Address=G, Join=S, Prune=NULL. When the (S,G) entry is created, the 222 outgoing interface list is copied from (*,G), i.e., all local shared 223 tree branches are replicated in the new shortest path tree. In this 224 way when a data packet from S arrives and matches on this entry, all 225 receivers will continue to receive the source's packets along this 226 path. (In more complicated scenarios, other entries in the router 227 have to be considered, as described in Section 3). Note that (S,G) 228 state must be maintained in each last-hop router that is responsible 229 for initiating and maintaining an SP-tree. Even when (*,G) and (S,G) 230 overlap, both states are needed to trigger the source-specific 231 Join/Prune messages. (S,G) state is kept alive by data packets 232 arriving from that source. A timer, Entry-timer, is set for the (S,G) 233 entry and this timer is restarted whenever data packets for (S,G) are 234 forwarded out at least one oif, or Registers are sent. When the 235 Entry-timer expires, the state is deleted. The last-hop router is the 236 router that delivers the packets to their ultimate end-system 237 destination. This is the router that monitors if there is group 238 membership and joins or prunes the appropriate distribution trees in 239 response. In general the last-hop router is the Designated Router 240 (DR) for the LAN. However, under various conditions described later, 241 a parallel router connected to the same LAN may take over as the 242 last-hop router in place of the DR. 244 Only the RP and routers with local members can initiate switching to 245 the SP-tree; intermediate routers do not. Consequently, last-hop 246 routers create (S,G) state in response to data packets from the 247 source, S; whereas intermediate routers only create (S,G) state in 248 response to Join/Prune messages from downstream that have S in the 249 Join list. 251 The (S,G) entry is initialized with the SPT-bit cleared, indicating 252 that the shortest path tree branch from S has not yet been setup 253 completely, and the router can still accept packets from S that 254 arrive on the (*,G) entry's indicated incoming interface (iif). Each 255 PIM multicast entry has an associated incoming interface on which 256 packets are expected to arrive. 258 When a router with a (S,G) entry and a cleared SPT-bit starts to 259 receive packets from the new source S on the iif for the (S,G) entry, 260 and that iif differs from the (*,G) entry's iif, the router sets the 261 SPT-bit, and sends a Join/Prune message towards the RP, indicating 262 that the router no longer wants to receive packets from S via the 263 shared RP-tree. The Join/Prune message sent towards the RP includes S 264 in the prune list, with the RPT-bit set indicating that S's packets 265 must not be forwarded down this branch of the shared tree. If the 266 router receiving the Join/Prune message has (S,G) state (with or 267 without the route entry's RPT-bit flag set), it deletes the arriving 268 interface from the (S,G) oif list. If the router has only (*,G) 269 state, it creates an entry with the RPT-bit flag set to 1. For 270 brevity we refer to an (S,G) entry that has the RPT-bit flag set to 1 271 as an (S,G)RPT-bit entry. This notational distinction is useful to 272 point out the different actions taken for (S,G) entries depending on 273 the setting of the RPT-bit flag. Note that a router can have no more 274 than one active (S,G) entry for any particular S and G, at any 275 particular time; whether the RPT-bit flag is set or not. In other 276 words, a router never has both an (S,G) and an (S,G)RPT-bit entry for 277 the same S and G at the same time. The Join/Prune message payload 278 contains Multicast-Address=G, Join=NULL, Prune=S,RPT-bit. 280 A new receiver may join an existing RP-tree on which source-specific 281 prune state has been established (e.g., because downstream receivers 282 have switched to SP-trees). In this case the prune state must be 283 eradicated upstream of the new receiver to bring all sources' data 284 packets down to the new receiver. Therefore, when a (*,G) Join 285 arrives at a router that has any (Si,G)RPT-bit entries (i.e., entries 286 that cause the router to send source-specific prunes toward the RP), 287 these entries must be updated upstream of the router so as to bring 288 all sources' packets down to the new member. To accomplish this, each 289 router that receives a (*,G) Join/Prune message updates all existing 290 (S,G)RPT-bit entries. The router may also trigger a (*,G) Join/Prune 291 message upstream to cause the same updating of RPT-bit settings 292 upstream and pull down all active sources' packets. If the arriving 293 (*,G) join has some sources included in its prune list, then the 294 corresponding (S,G)RPT-bit entries are left unchanged (i.e., the 295 RPT-bit remains set and no oif is added). 297 2.5 Steady state maintenance of distribution tree (i.e., router state)} 299 In the steady state each router sends periodic Join/Prune messages 300 for each active PIM route entry; the Join/Prune messages are sent to 301 the neighbor indicated in the corresponding entry. These messages are 302 sent periodically to capture state, topology, and membership changes. 303 A Join/Prune message is also sent on an event-triggered basis each 304 time a new route entry is established for some new source (note that 305 some damping function may be applied, e.g., a short delay to allow 306 for merging of new Join information). Join/Prune messages do not 307 elicit any form of explicit acknowledgment; routers recover from lost 308 packets using the periodic refresh mechanism. 310 2.6 Obtaining RP information 312 To obtain the RP information, all routers within a PIM domain collect 313 Bootstrap messages. Bootstrap messages are sent hop-by-hop within the 314 domain; the domain's bootstrap router (BSR) is responsible for 315 originating the Bootstrap messages. Bootstrap messages are used to 316 carry out a dynamic BSR election when needed and to distribute RP 317 information in steady state. 319 A domain in this context is a contiguous set of routers that all 320 implement PIM and are configured to operate within a common boundary 321 defined by PIM Multicast Border Routers (PMBRs). PMBRs connect each 322 PIM domain to the rest of the internet. 324 Routers use a set of available RPs (called the RP-Set) distributed 325 in Bootstrap messages to get the proper Group to RP mapping. The 326 following paragraphs summarize the mechanism; details of the 327 mechanism may be found in Sections 3.6 and Appendix 6.2. A (small) 328 set of routers, within a domain, are configured as candidate BSRs 329 and, through a simple election mechanism, a single BSR is selected 330 for that domain. A set of routers within a domain are also configured 331 as candidate RPs (C-RPs); typically these will be the same routers 332 that are configured as C-BSRs. Candidate RPs periodically unicast 333 Candidate-RP-Advertisement messages (C-RP-Advs) to the BSR of that 334 domain. C-RP-Advs include the address of the advertising C-RP, as 335 well as an optional group address and a mask length field, indicating 336 the group prefix(es) for which the candidacy is advertised. The BSR 337 then includes a set of these Candidate-RPs (the RP-Set), along with 338 the corresponding group prefixes, in Bootstrap messages it 339 periodically originates. Bootstrap messages are distributed hop-by- 340 hop throughout the domain. 342 Routers receive and store Bootstrap messages originated by the BSR. 343 When a DR gets a membership indication from IGMP for (or a data 344 packet from) a directly connected host, for a group for which it has 345 no entry, the DR uses a hash function to map the group address to one 346 of the C-RPs whose Group-prefix includes the group (see Section 347 3.7). The DR then sends a Join/Prune message towards (or unicasts 348 Registers to) that RP. 350 The Bootstrap message indicates liveness of the RPs included therein. 351 If an RP is included in the message, then it is tagged as `up' at the 352 routers; while RPs not included in the message are removed from the 353 list of RPs over which the hash algorithm acts. Each router continues 354 to use the contents of the most recently received Bootstrap message 355 until it receives a new Bootstrap message. 357 If a PIM domain partitions, each area separated from the old BSR will 358 elect its own BSR, which will distribute an RP-Set containing RPs 359 that are reachable within that partition. When the partition heals, 360 another election will occur automatically and only one of the BSRs 361 will continue to send out Bootstrap messages. As is expected at the 362 time of a partition or healing, some disruption in packet delivery 363 may occur. This time will be on the order of the region's round-trip 364 time and the bootstrap router timeout value. 366 2.7 Interoperation with dense mode protocols such as DVMRP 368 In order to interoperate with networks that run dense-mode, 369 broadcast and prune, protocols, such as DVMRP, all packets generated 370 within a PIM-SM region must be pulled out to that region's PIM 371 Multicast Border Routers (PMBRs) and injected (i.e., broadcast) into 372 the DVMRP network. A PMBR is a router that sits at the boundary of a 373 PIM-SM domain and interoperates with other types of multicast routers 374 such as those that run DVMRP. Generally a PMBR would speak both 375 protocols and implement interoperability functions not required by 376 regular PIM routers. To support interoperability, a special entry 377 type, referred to as (*,*,RP), must be supported by all PIM routers. 378 For this reason we include details about (*,*,RP) entry handling in 379 this general PIM specification. 381 A data packet will match on a (*,*,RP) entry if there is no more 382 specific entry (such as (S,G) or (*,G)) and the destination group 383 address in the packet maps to the RP listed in the (*,*,RP) entry. In 384 this sense, a (*,*,RP) entry represents an aggregation of all the 385 groups that hash to that RP. PMBRs initialize (*,*,RP) state for each 386 RP in the domain's RPset. The (*,*,RP) state causes the PMBRs to send 387 (*,*,RP) Join/Prune messages toward each of the active RPs in the 388 domain. As a result distribution trees are built that carry all data 389 packets originated within the PIM domain (and sent to the RPs) down 390 to the PMBRs. 392 PMBRs are also responsible for delivering externally-generated 393 packets to routers within the PIM domain. To do so, PMBRs initially 394 encapsulate externally-originated packets (i.e., received on DVMRP 395 interfaces) in Register messages and unicast them to the 396 corresponding RP within the PIM domain. The Register message has a 397 bit indicating that it was originated by a border router and the RP 398 caches the originating PMBR's address in the route entry so that 399 duplicate Registers from other PMBRs can be declined with a 400 Register-Stop message. 402 All PIM routers must be capable of supporting (*,*,RP) state and 403 interpreting associated Join/Prune messages. We describe the handling 404 of (*,*,RP) entries and messages throughout this document; however, 405 detailed PIM Multicast Border Router (PMBR) functions will be 406 specified in a separate interoperability document (see directory, 407 http://catarina.usc.edu/pim/interop/). 409 2.8 Multicast data packet processing 411 Data packets are processed in a manner similar to other multicast 412 schemes. A router first performs a longest match on the source and 413 group address in the data packet. A (S,G) entry is matched first if 414 one exists; a (*,G) entry is matched otherwise. If neither state 415 exists, then a (*,*,RP) entry match is attempted as follows: the 416 router hashes on G to identify the RP for group G, and looks for a 417 (*,*,RP) entry that has this RP address associated with it. If none 418 of the above exists, then the packet is dropped. If a state is 419 matched, the router compares the interface on which the packet 420 arrived to the incoming interface field in the matched route entry. 421 If the iif check fails the packet is dropped, otherwise the packet is 422 forwarded to all interfaces listed in the outgoing interface list. 424 Some special actions are needed to deliver packets continuously while 425 switching from the shared to shortest-path tree. In particular, when 426 a (S,G) entry is matched, incoming packets are forwarded as follows: 428 1 If the SPT-bit is set, then: 430 1 if the incoming interface is the same as a matching 431 (S,G) iif, the packet is forwarded to the oif-list of 432 (S,G). 434 2 if the incoming interface is different than a matching 435 (S,G) iif , the packet is discarded. 437 2 If the SPT-bit is cleared, then: 439 1 if the incoming interface is the same as a matching 440 (S,G) iif, the packet is forwarded to the oif-list of 441 (S,G). In addition, the SPT bit is set for that entry 442 if the incoming interface differs from the incoming 443 interface of the (*,G) or (*,*,RP) entry. 445 2 if the incoming interface is different than a matching 446 (S,G) iif, the incoming interface is tested against a 447 matching (*,G) or (*,*,RP) entry. If the iif is the 448 same as one of those, the packet is forwarded to the 449 oif-list of the matching entry. 451 3 Otherwise the iif does not match any entry for G and 452 the packet is discarded. 454 Data packets never trigger prunes. However, data packets may 455 trigger actions that in turn trigger prunes. For example, when 456 router B in figure 3 decides to switch to SP-tree at step 3, it 457 creates a (S,G) entry with SPT-bit set to 0. When data packets 458 from S arrive at interface 2 of B, B sets the SPT-bit to 1 459 since the iif for (*,G) is different than that for (S,G). This 460 triggers the sending of prunes towards the RP. 462 2.9 Operation over Multi-access Networks 464 This section describes a few additional protocol mechanisms 465 needed to operate PIM over multi-access networks: Designated 466 Router election, Assert messages to resolve parallel paths, and 467 the Join/Prune-Suppression-Timer to suppress redundant Joins on 468 multi-access networks. 470 Designated router election: 472 When there are multiple routers connected to a multi-access 473 network, one of them must be chosen to operate as the designated 474 router (DR) at any point in time. The DR is responsible for 475 sending triggered Join/Prune and Register messages toward the 476 RP. 478 A simple designated router (DR) election mechanism is used for 479 both SM and traditional IP multicast routing. Neighboring 480 routers send Hello messages to each other. The sender with the 481 largest network layer address assumes the role of DR. Each 482 router connected to the multi-access LAN sends the Hellos 483 periodically in order to adapt to changes in router status. 485 Parallel paths to a source or the RP--Assert process: 487 If a router receives a multicast datagram on a multi-access LAN 488 from a source whose corresponding (S,G) outgoing interface list 489 includes the interface to that LAN, the packet must be a 490 duplicate. In this case a single forwarder must be elected. 491 Using Assert messages addressed to `224.0.0.13' (ALL-PIM-ROUTERS 492 group) on the LAN, upstream routers can resolve which one will 493 act as the forwarder. Downstream routers listen to the Asserts 494 so they know which one was elected, and therefore where to send 495 subsequent Joins. Typically this is the same as the downstream 496 router's RPF (Reverse Path Forwarding) neighbor; but there are 497 circumstances where this might not be the case, e.g., when using 498 multiple unicast routing protocols on that LAN. The RPF neighbor 499 for a particular source (or RP) is the next-hop router to which 500 packets are forwarded en route to that source (or RP); and 501 therefore is considered a good path via which to accept packets 502 from that source. 504 The upstream router elected is the one that has the shortest 505 distance to the source. Therefore, when a packet is received on 506 an outgoing interface a router sends an Assert message on the 507 multi-access LAN indicating what metric it uses to reach the 508 source of the data packet. The router with the smallest 509 numerical metric (with ties broken by highest address) will 510 become the forwarder. All other upstream routers will delete the 511 interface from their outgoing interface list. The downstream 512 routers also do the comparison in case the forwarder is 513 different than the RPF neighbor. 515 Associated with the metric is a metric preference value. This is 516 provided to deal with the case where the upstream routers may 517 run different unicast routing protocols. The numerically smaller 518 metric preference is always preferred. The metric preference is 519 treated as the high-order part of an assert metric comparison. 520 Therefore, a metric value can be compared with another metric 521 value provided both metric preferences are the same. A metric 522 preference can be assigned per unicast routing protocol and 523 needs to be consistent for all routers on the multi-access 524 network. 526 Asserts are also needed for (*,G) entries since an RP-Tree and 527 an SP-Tree for the same group may both cross the same multi- 528 access network. When an assert is sent for a (*,G) entry, the 529 first bit in the metric preference (RPT-bit) is always set to 1 530 to indicate that this path corresponds to the RP tree, and that 531 the match must be done on (*,G) if it exists. Furthermore, the 532 RPT-bit is always cleared for metric preferences that refer to 533 SP-tree entries; this causes an SP-tree path to always look 534 better than an RP-tree path. When the SP-tree and RPtree cross 535 the same LAN, this mechanism eliminates the duplicates that 536 would otherwise be carried over the LAN. 538 In case the packet, or the Assert message, matches on oif for 539 (*,*,RP) entry, a (*,G) entry is created, and asserts take place 540 as if the matching state were (*,G). 542 The DR may lose the (*,G) Assert process to another router on 543 the LAN if there are multiple paths to the RP through the LAN. 544 From then on, the DR is no longer the last-hop router for local 545 receivers and removes the LAN from its (*,G) oif list. The 546 winning router becomes the last-hop router and is responsible 547 for sending (*,G) join messages to the RP. 549 Join/Prune suppression: 551 Join/Prune suppression may be used on multi-access LANs to 552 reduce duplicate control message overhead; it is not required 553 for correct performance of the protocol. If a Join/Prune message 554 arrives and matches on the incoming interface for an existing 555 (S,G), (*,G), or (*,*,RP) route entry, and the Holdtime included 556 in the Join/Prune message is greater than the recipient's own 557 [Join/Prune-Holdtime] (with ties resolved in favor of the higher 558 network layer address), a timer (the Join/Prune-Suppression- 559 timer) in the recipient's route entry may be started to suppress 560 further Join/Prune messages. After this timer expires, the 561 recipient triggers a Join/Prune message, and resumes sending 562 periodic Join/Prunes, for this entry. The Join/Prune- 563 Suppression-timer should be restarted each time a Join/Prune 564 message is received with a higher Holdtime. 566 2.10 Unicast Routing Changes 568 When unicast routing changes, an RPF check is done on all active 569 (S,G), (*,G) and (*,*,RP) entries, and all affected expected 570 incoming interfaces are updated. In particular, if the new 571 incoming interface appears in the outgoing interface list, it is 572 deleted from the outgoing interface list. The previous incoming 573 interface may be added to the outgoing interface list by a 574 subsequent Join/Prune from downstream. Join/Prune messages 575 received on the current incoming interface are ignored. 576 Join/Prune messages received on new interfaces or existing 577 outgoing interfaces are not ignored. Other outgoing interfaces 578 are left as is until they are explicitly pruned by downstream 579 routers or are timed out due to lack of appropriate Join/Prune 580 messages. If the router has a (S,G) entry with the SPT-bit set, 581 and the updated iif(S,G) does not differ from iif(*,G) or 582 iif(*,*,RP), then the router resets the SPT-bit. 584 The router must send a Join/Prune message with S in the Join 585 list out any new incoming interfaces to inform upstream routers 586 that it expects multicast datagrams over the interface. It may 587 also send a Join/Prune message with S in the Prune list out the 588 old incoming interface, if the link is operational, to inform 589 upstream routers that this part of the distribution tree is 590 going away. 592 2.11 PIM-SM for Inter-Domain Multicast 594 Future documents will address the use of PIM-SM as a backbone 595 inter-domain multicast routing protocol. Design choices center 596 primarily around the distribution and usage of RP information 597 for wide area, inter-domain groups. 599 2.12 Security 601 All PIM control messages may use IPsec [6] to address security 602 concerns. Security mechanisms are likely to be enhanced in the 603 near future. 605 3 Detailed Protocol Description 607 This section describes the protocol operations from the 608 perspective of an individual router implementation. In 609 particular, for each message type we describe how it is 610 generated and processed. 612 3.1 Hello 614 Hello messages are sent so neighboring routers can discover each 615 other. 617 3.1.1 Sending Hellos 619 Hello messages are sent periodically between PIM neighbors, 620 every [Hello-Period] seconds. This informs routers what 621 interfaces have PIM neighbors. Hello messages are multicast 622 using address 224.0.0.13 (ALL-PIM-ROUTERS group). The packet 623 includes a Holdtime, set to [Hello-Holdtime], for neighbors to 624 keep the information valid. Hellos are sent on all types of 625 communication links. 627 3.1.2 Receiving Hellos 629 When a router receives a Hello message, it stores the network 630 layer address for that neighbor, sets its Neighbor-timer for the 631 Hello sender to the Holdtime included in the Hello, and 632 determines the Designated Router (DR) for that interface. The 633 highest addressed system is elected DR. Each Hello received 634 causes the DR's address to be updated. 636 When a router that is the active DR receives a Hello from a new 637 neighbor (i.e., from an address that is not yet in the DRs 638 neighbor table), the DR unicasts its most recent RP-set 639 information to the new neighbor. 641 3.1.3 Timing out neighbor entries 643 A periodic process is run to time out PIM neighbors that have 644 not sent Hellos. If the DR has gone down, a new DR is chosen by 645 scanning all neighbors on the interface and selecting the new DR 646 to be the one with the highest network layer address. If an 647 interface has gone down, the router may optionally time out all 648 PIM neighbors associated with the interface. 650 3.2 Join/Prune 652 Join/Prune messages are sent to join or prune a branch off of 653 the multicast distribution tree. A single message contains both 654 a join and prune list, either one of which may be null. Each 655 list contains a set of source addresses, indicating the source- 656 specific trees or shared tree that the router wants to join or 657 prune. 659 3.2.1 Sending Join/Prune Messages 661 Join/Prune messages are merged such that a message sent to a 662 particular upstream neighbor, N, includes all of the current 663 joined and pruned sources that are reached via N; according to 664 unicast routing Join/Prune messages are multicast to all routers 665 on multi-access networks with the target address set to the next 666 hop router towards S or RP. Join/Prune messages are sent every 667 [Join/Prune-Period] seconds. In the future we will introduce 668 mechanisms to rate-limit this control traffic on a hop by hop 669 basis, in order to avoid excessive overhead on small links. In 670 addition, certain events cause triggered Join/Prune messages to 671 be sent. 673 Periodic Join/Prune Messages: 675 A router sends a periodic Join/Prune message to each distinct 676 RPF neighbor associated with each (S,G), (*,G) and (*,*,RP) 677 entry. Join/Prune messages are only sent if the RPF neighbor is 678 a PIM neighbor. A periodic Join/Prune message sent to a 679 particular RPF neighbor is constructed as follows: 681 1 Each router determines the RP for a (*,G) entry by using 682 the hash function described. The RP address (with RPT and 683 WC bits set) is included in the join list of a periodic 684 Join/Prune message under the following conditions: 686 1 The Join/Prune message is being sent to the RPF 687 neighbor toward the RP for an active (*,G) or (*,*,RP) 688 entry, and 690 2 The outgoing interface list in the (*,G) or (*,*,RP) 691 entry is non-NULL, or the router is the DR on the same 692 interface as the RPF neighbor. 694 2 A particular source address, S, is included in the join 695 list with the RPT and WC bits cleared under the following 696 conditions: 698 1 The Join/Prune message is being sent to the RPF 699 neighbor toward S, and 701 2 There exists an active (S,G) entry with the RPT-bit 702 flag cleared, and 704 3 The oif list in the (S,G) entry is not null. 706 3 A particular source address, S, is included in the prune 707 list with the RPT and WC bits cleared under the following 708 conditions: 710 1 The Join/Prune message is being sent to the RPF 711 neighbor toward S, and 713 2 There exists an active (S,G) entry with the RPT-bit 714 flag cleared, and 716 3 The oif list in the (S,G) entry is null. 718 4 A particular source address, S, is included in the prune 719 list with the RPT-bit set and the WC bit cleared under the 720 following conditions: 722 1 The Join/Prune message is being sent to the RPF 723 neighbor toward the RP and there exists a (S,G) entry 724 with the RPT-bit flag set and null oif list, or 726 2 The Join/Prune message is being sent to the RPF 727 neighbor toward the RP, there exists a (S,G) entry 728 with the RPT-bit flag cleared and SPT-bit set, and the 729 incoming interface toward S is different than the 730 incoming interface toward the RP, or 732 3 The Join/Prune message is being sent to the RPF 733 neighbor toward the RP, and there exists a (*,G) entry 734 and (S,G) entry for a directly connected source. 736 5 The RP address (with RPT and WC bits set) is included in 737 the prune list if: 739 1 The Join/Prune message is being sent to the RPF 740 neighbor toward the RP and there exists a (*,G) entry 741 with a null oif list (see Section 3.5.2). 743 Triggered Join/Prune Messages: 745 In addition to periodic messages, the following events will 746 trigger Join/Prune messages if as a result, a) a new entry is 747 created, or b) the oif list changes from null to non-null or 748 non-null to null. The contents of triggered messages are the 749 same as the periodic, described above. 751 1 Receipt of an indication from IGMP that the state of 752 directly-connected- membership has changed (i.e., new 753 members have just joined `membership indication' or all 754 members have left), for a group G, may cause the last-hop 755 router to build or modify corresponding (*,G) state. When 756 IGMP indicates that there are no longer directly connected 757 members, the oif is removed from the oif list if the oif- 758 timer is not running. A Join/Prune message is triggered if 759 and only if a) a new entry is created, or b) the oif list 760 changes from null to non-null or non-null to null, as 761 follows : 763 1 If the receiving router does not have a route entry 764 for G the router creates a (*,G) entry, copies the oif 765 list from the corresponding (*,*,RP) entry (if it 766 exists), and includes the interface included in the 767 IGMP membership indication in the oif list; as always, 768 the router never includes the entry's iif in the oif 769 list. The router sends a Join/Prune message towards 770 the RP with the RP address and RPT-bit and WC-bits set 771 in the join list. Or, 773 2 If a (S,G)RPT-bit or (*,G) entry already exists, the 774 interface included in the IGMP membership indication 775 is added to the oif list (if it was not included 776 already). 778 2 Receipt of a Join/Prune message for (S,G), (*,G) or 779 (*,*,RP) will cause building or modifying corresponding 780 state, and subsequent triggering of upstream Join/Prune 781 messages, in the following cases: 783 1 When there is no current route entry, the RP address 784 included in the Join/Prune message is checked against 785 the local RP-Set information. If it matches, an entry 786 will be created and the new entry will in turn trigger 787 an upstream Join/Prune message. If the router has no 788 RP-Set information it may discard the message, or 789 optionally use the RP address included in the message. 791 2 When the outgoing interface list of an (S,G)RPT-bit 792 entry becomes null, the triggered Join/Prune message 793 will contain S in the prune list. 795 3 When there exists a (S,G)RPT-bit with null oif list, 796 and an (*,G) Join/Prune message is received, the 797 arriving interface is added to the oif list and a 798 (*,G) Join/Prune message is triggered upstream. 800 4 When there exists a (*,G) with null oif list, and a 801 (*,*,RP) Join/Prune message is received, the receiving 802 interface is added to the oif list and a (*,*,RP) 803 Join/Prune message is triggered upstream. 805 3 Receipt of a packet that matches on a (S,G) entry whose 806 SPT-bit is cleared triggers the following if the packet 807 arrived on the correct incoming interface and there is a 808 (*,G) or (*,*,RP) entry with a different incoming 809 interface: a) the router sets the SPT-bit on the (S,G) 810 entry, and b) the router sends a Join/Prune message towards 811 the RP with S in the prune list and the RPT-bit set. 813 4 Receipt of a packet at the DR from a directly connected 814 source S, on the subnet containing the address S, triggers 815 a Join/Prune message towards the RP with S in the prune 816 list and the RPT-bit set under the following conditions: a) 817 there is no matching (S,G) state, and b) there exists a 818 (*,G) or (*,*,RP) for which the DR is not the RP. 820 5 When a Join/Prune message is received for a group G, the 821 prune list is checked. If the prune list contains a source 822 or RP for which the receiving router has a corresponding 823 active (S,G), (*,G) or (*,*,RP) entry, and whose iif is 824 that on which the Join/Prune was received, then a join for 825 (S,G), (*,G) or (*,*,RP) is triggered to override the 826 prune, respectively. (This is necessary in the case of 827 parallel downstream routers connected to a multi-access 828 network.) 830 6 When the RP fails, the RP will not be included in the 831 Bootstrap messages sent to all routers in that domain. This 832 triggers the DRs to send (*,G) Join/Prune messages towards 833 the new RP for the group, as determined by the RP-Set and 834 the hash function. As described earlier, PMBRs trigger 835 (*,*,RP) joins towards each RP in the RP-Set. 837 7 When an entry's Join/Prune-Suppression timer expires, a 838 Join/Prune message is triggered upstream corresponding to 839 that entry, even if the outgoing interface has not 840 transitioned between null and non-null states. 842 8 When the RPF neighbor changes (whether due to an Assert or 843 changes in unicast routing), the router sets a random delay 844 timer (the Random-Delay-Join-Timer) whose expiration 845 triggers sending of a Join/Prune message for the asserted 846 route entry to the Assert winner (if the Join/Prune 847 Suppression timer has expired.) 849 We do not trigger prunes onto interfaces based on data packets. 850 Data packets that arrive on the wrong incoming interface are 851 silently dropped. However, on point-to-point interfaces 852 triggered prunes may be sent as an optimization. 854 aragraphFragmentation It is possible that a Join/Prune message 855 constructed according to the preceding rules could exceed the 856 MTU of a network. In this case, the message can undergo semantic 857 fragmentation whereby information corresponding to different 858 groups can be sent in different messages. However, if a 859 Join/Prune message must be fragmented the complete prune list 860 corresponding to a group G must be included in the same 861 Join/Prune message as the associated RP-tree Join for G. If such 862 semantic fragmentation is not possible, IP fragmentation should 863 be used between the two neighboring hops. 865 3.2.2 Receiving Join/Prune Messages When a router receives a 866 Join/Prune message, it processes it as follows. 868 The receiver of the Join/Prune notes the interface on which the 869 PIM message arrived, call it I. The receiver then checks to see 870 if the Join/Prune message was addressed to the receiving router 871 itself (i.e., the router's address appears in the Unicast 872 Upstream Neighbor Router field of the Join/Prune message). (If 873 the router is connected to a multiaccess LAN, the message could 874 be intended for a different router.) If the Join/Prune is for 875 this router the following actions are taken. 877 For each group address G, in the Join/Prune message, the 878 associated join list is processed as follows. We refer to each 879 address in the join list as Sj; Sj refers to the RP if the RPT- 880 bit and WC-bit are both set. For each Sj in the join list of the 881 Join/Prune message: 883 1 If an address, Sj, in the join list of the Join/Prune 884 message has the RPT-bit and WC-bit set, then Sj is the RP 885 address used by the downstream router(s) and the following 886 actions are taken: 888 1 If Sj is not the same as the receiving router's RP 889 mapping for G, the receiving router may ignore the 890 Join/Prune message with respect to that group entry. 891 If the router does not have any RP-Set information, it 892 may use the address Sj included in the Join/Prune 893 message as the RP for the group. 895 2 If Sj is the same as the receiving router's RP mapping 896 for G, the receiving router adds I to the outgoing 897 interface list of the (*,G) route entry (if there is 898 no (*,G) entry, the router creates one first) and sets 899 the Oif-timer for that interface to the Holdtime 900 specified in the Join/Prune message. In addition, the 901 Oif-Deletion-Delay for that interface is set to 1/3rd 902 the Holdtime specified in the Join/Prune message. If a 903 (*,*,RP) entry exists, for the RP associated with G, 904 then the oif list of the newly created (*,G) entry is 905 copied from that (*,*,RP) entry. 907 3 For each (Si,G) entry associated with group G: i) if 908 Si is not included in the prune list, ii) if I is not 909 on the same subnet as the address Si, and iii) if I is 910 not the iif, then interface I is added to the oif 911 list and the Oif-timer for that interface in each 912 affected entry is increased (never decreased) to the 913 Holdtime included in the Join/Prune message. In 914 addition, if the Oif-timer for that interface is 915 increased, the Oif-Deletion-Delay for that interface 916 is set to 1/3rd the Holdtime specified in the 917 Join/Prune message. 919 If the group address in the Join/Prune message is `*' 920 then every (*,G) and (S,G) entry, whose group address 921 hashes to the RP indicated in the (*,*,RP) Join/Prune 922 message, is updated accordingly. A `*' in the group 923 field of the Join/Prune is represented by a group 924 address 224.0.0.0 and a group mask length of 4, 925 indicating a (*,*,RP) Join. 927 4 If the (Si,G) entry has its RPT-bit flag set to 1, and 928 its oif list is the same as the (*,G) oif 929 list, then the (Si,G)RPT-bit entry is deleted, 931 5 The incoming interface is set to the interface used to 932 send unicast packets to the RP in the (*,G) route 933 entry, i.e., RPF interface toward the RP. 935 2 For each address, Sj, in the join list whose RPT-bit and 936 WC-bit are not set, and for which there is no existing 937 (Sj,G) route entry, the router initiates one. The router 938 creates a (S,G) entry and copies all outgoing interfaces 939 from the (S,G)RPT-bit entry, if it exists. If there is no 940 (S,G) entry, the oif list is copied from the (*,G) entry; 941 and if there is no (*,G) entry, the oif list is copied from 942 the (*,*,RP) entry, if it exists. In all cases, the iif of 943 the (S,G) entry is always excluded from the oif list. 945 1 The outgoing interface for (Sj,G) is set to I. The 946 incoming interface for (Sj,G) is set to the interface 947 used to send unicast packets to Sj (i.e., the RPF 948 neighbor). 950 2 If the interface used to reach Sj, is the same as I, 951 this represents an error (or a unicast routing change) 952 and the Join/Prune must not be processed. 954 3 For each address, Sj, in the join list of the Join/Prune 955 message, for which there is an existing (Sj,G) route entry, 957 1 If the RPT-bit is not set for Sj listed in the 958 Join/Prune message, but the RPT-bit flag is set on the 959 existing (Sj,G) entry, the router clears the RPT-bit 960 flag on the (Sj,G) entry, sets the incoming interface 961 to point towards Sj for that (Sj,G) entry, and sends a 962 Join/Prune message corresponding to that entry through 963 the new incoming interface; and 965 2 If I is not the same as the existing incoming 966 interface, the router adds I to the list of outgoing 967 interfaces. 969 3 The Oif-timer for I is increased (never decreased) to 970 the Holdtime included in the Join/Prune message. In 971 addition, if the Oif-timer for that interface is 972 increased, the Oif-Deletion-Delay for that interface 973 is set to 1/3rd the Holdtime specified in the 974 Join/Prune message. 976 4 The (Sj,G) entry's SPT bit is cleared until data comes 977 down the shortest path tree. 979 For each group address G, in the Join/Prune message, the 980 associated prune list is processed as follows. We refer to each 981 address in the prune list as Sp; Sp refers to the RP if the 982 RPT-bit and WC-bit are both set. For each Sp in the prune list 983 of the Join/Prune message: 985 1 For each address, Sp, in the prune list whose RPT-bit and 986 WC-bit are cleared: 988 1 If there is an existing (Sp,G) route entry, the router 989 lowers the entry's Oif-timer for I to its Oif- 990 Deletion-Delay, allowing for other downstream routers 991 on a multi-access LAN to override the prune. However, 992 on point-to-point links, the oif-timer is expired 993 immediately. 995 2 If the router has a current (*,G), or (*,*,RP), route 996 entry, and if the existing (Sp,G) entry has its RPT- 997 bit flag set to 1, then this (Sp,G)RPT-bit entry is 998 maintained (not deleted) even if its outgoing 999 interface list is null. 1001 2 For each address, Sp, in the prune list whose RPT-bit is 1002 set and whose WC-bit cleared: 1004 1 If there is an existing (Sp,G) route entry, the router 1005 lowers the entry's Oif-timer for I to its Oif- 1006 Deletion-Delay, allowing for other downstream routers 1007 on a multi-access LAN to override the prune. However, 1008 on point-to-point links, the oif-timer is expired 1009 immediately. 1011 2 If the router has a current (*,G), or (*,*,RP), route 1012 entry, and if the existing (Sp,G) entry has its RPT- 1013 bit flag set to 1, then this (Sp,G)RPT-bit entry is 1014 not deleted, and the Entry-timer is restarted, even if 1015 its outgoing interface list is null. 1017 3 If (*,G), or corresponding (*,*,RP), state exists, but 1018 there is no (Sp,G) entry, an (Sp,G)RPT-bit entry is 1019 created . The outgoing interface list is copied from 1020 the (*,G), or (*,*,RP), entry, with the interface, I, 1021 on which the prune was received, is deleted. Packets 1022 from the pruned source, Sp, match on this state and 1023 are not forwarded toward the pruned receivers. 1025 4 If there exists a (Sp,G) entry, with or without the 1026 RPT-bit set, the oif-timer for I is expired, and the 1027 Entry-timer is restarted. 1029 3 For each address, Sp, in the prune list whose RPT-bit and 1030 WC-bit are both set: 1032 1 If there is an existing (*,G) entry, with Sp as the RP 1033 for G, the router lowers the entry's Oif-timer for I 1034 to its Oif-Deletion-Delay, allowing for other 1035 downstream routers on a multi-access LAN to override 1036 the prune. However, on point-to-point links, the oif- 1037 timer is expired immediately. 1039 2 If the corresponding (*,*,RP) state exists, but there 1040 is no (*,G) entry, a (*,G) entry is created. The 1041 outgoing interface list is copied from (*,*,RP) entry, 1042 with the interface, I, on which the prune was 1043 received, deleted. 1045 For any new (S,G), (*,G) or (*,*,RP) entry created by an 1046 incoming Join/Prune message, the SPT-bit is cleared (and if 1047 a Join/Prune-Suppression timer is used, it is left off.) 1049 If the entry has a Join/Prune-Suppression timer associated with 1050 it, and if the received Join/Prune does not indicate the router 1051 as its target, then the receiving router examines the join and 1052 prune lists to see if any addresses in the list `completely- 1053 match' existing (S,G), (*,G), or (*,*,RP) state for which the 1054 receiving router currently schedules Join/Prune messages. An 1055 element on the join or prune list `completely-matches' a route 1056 entry only if both the addresses and RPT-bit flag are the same. 1057 If the incoming Join/Prune message completely matches an 1058 existing (S,G), (*,G), or (*,*,RP) entry and the Join/Prune 1059 arrived on the iif for that entry, then the router compares 1060 the Holdtime included in the Join/Prune message, to its own 1061 [Join/Prune-Holdtime]. If its own [Join/Prune-Holdtime] is 1062 lower, the Join/Prune-Suppression-timer is started at the 1063 [Join/Prune-Suppression-Timeout]. If the [Join/Prune-Holdtime] 1064 is equal, the tie is resolved in favor of the Join/Prune Message 1065 originator that has the higher network layer address. When the 1066 Join/Prune timer expires, the router triggers a Join/Prune 1067 message for the corresponding entry(ies). 1069 3.3 Register and Register-Stop 1071 When a source first starts sending to a group its packets are 1072 encapsulated in Register messages and sent to the RP. If the 1073 data rate warrants source-specific paths, the RP sets up source 1074 specific state and starts sending (S,G) Join/Prune messages 1075 toward the source, with S in the join list. 1077 3.3.1 Sending Registers and Receiving Register-Stops 1079 Register messages are sent as follows: 1081 1 When a DR receives a packet from a directly connected 1082 source, S, on the subnet containing the address S, 1084 1 If there is no corresponding (S,G) entry, and the 1085 router has RP-Set information, and the DR is not the 1086 RP for G, the DR creates an (S,G) entry with the 1087 Register-Suppression-timer turned off and the RP 1088 address set according to the hash function mapping for 1089 the corresponding group. The oif list is copied from 1090 existing (*,G) or (*,*,RP) entries, if they exist. The 1091 iif of the (S,G) entry is always excluded from the oif 1092 list. If there exists a (*,G) or (*,*,RP) entry, the 1093 DR sends a Join/Prune message towards the RP with S in 1094 the prune list and the RPT-bit set. 1096 2 If there is a (S,G) entry in existence, the DR simply 1097 restarts the corresponding Entry-timer. 1099 When a PMBR (e.g., a router that connects the PIM-SM region 1100 to a dense mode region running DVMRP or PIM-DM) receives a 1101 packet from a source in the dense mode region, the router 1102 treats the packet as if it were from a directly connected 1103 source. A separate document will describe the details of 1104 interoperability. 1106 2 If the new or previously-existing (S,G) entry's Register- 1107 Suppression-timer is not running, the data packet is 1108 encapsulated in a Register message and unicast to the RP 1109 for that group. The data packet is also forwarded according 1110 to (S,G) state in the DR if the oif list is not null; since 1111 a receiver may join the SP-tree while the DR is still 1112 registering to the RP. 1114 3 If the (S,G) entry's Register-Suppression-timer is running, 1115 the data packet is not sent in a Register message, it is 1116 just forwarded according to the (S,G) oif list. 1118 When the DR receives a Register-Stop message, it restarts the 1119 Register-Suppression-timer in the corresponding (S,G) entry(ies) 1120 at [Register-Suppression-Timeout] seconds. If there is data to 1121 be registered, the DR may send a null Register (a Register 1122 message with a zero-length data portion in the inner packet) to 1123 the RP, [Probe-Time] seconds before the Register-Suppression- 1124 timer expires, to avoid sending occasional bursts of traffic to 1125 an RP unnecessarily. 1127 3.3.2 Receiving Register Messages and Sending Register-Stops 1129 When a router (i.e., the RP) receives a Register message, the 1130 router does the following: 1132 1 Decapsulates the data packet, and checks for a 1133 corresponding (S,G) entry. 1135 1 If a (S,G) entry with cleared (0) SPT bit exists, and 1136 the received Register does not have the Null- 1137 Register-Bit set to 1, the packet is forwarded; and 1138 the SPT bit is left cleared (0). If the SPT bit is 1, 1139 the packet is dropped, and Register-Stop messages are 1140 triggered. Register-Stops should be rate-limited (in 1141 an implementation-specific manner) so that no more 1142 than a few are sent per round trip time. This prevents 1143 a high datarate stream of packets from triggering a 1144 large number of Register-Stop messages between the 1145 time that the first packet is received and the time 1146 when the source receives the first Register-Stop. 1148 2 If there is no (S,G) entry, but there is a (*,G) 1149 entry, and the received Register does not have the 1150 Null-Register-Bit set to 1, the packet is forwarded 1151 according to the (*,G) entry. 1153 3 If there is a (*,*,RP) entry but no (*,G) entry, and 1154 the Register received does not have the Null- 1155 Register-Bit set to 1, a (*,G) or (S,G) entry is 1156 created and the oif list is copied from the (*,*,RP) 1157 entry to the new entry. The packet is forwarded 1158 according to the created entry. 1160 4 If there is no G or (*,*,RP) entry corresponding to G, 1161 the packet is dropped, and a Register-Stop is 1162 triggered. 1164 5 A ``Border bit'' bit is added to the Register message, 1165 to facilitate interoperability mechanisms. PMBRs set 1166 this bit when registering for external sources (see 1167 Section 2.7). If the ``Border bit'' is set in the 1168 Register, the RP does the following: 1170 1 If there is no matching (S,G) state, but there 1171 exists (*,G) or (*,*,RP) entry, the RP creates a 1172 (S,G) entry, with a `PMBR' field. This field 1173 holds the source of the Register (i.e. the outer 1174 network layer address of the register packet). 1175 The RP triggers a (S,G) join towards the source 1176 of the data packet, and clears the SPT bit for 1177 the (S,G) entry. If the received Register is not 1178 a `null Register' the packet is forwarded 1179 according to the created state. Else, 1181 2 If the `PMBR' field for the corresponding (S,G) 1182 entry matches the source of the Register packet, 1183 and the received Register is not a `null 1184 Register', the decapsulated packet is forwarded 1185 to the oif list of that entry. Else, 1187 3 If the `PMBR' field for the corresponding (S,G) 1188 entry matches the source of the Register packet, 1189 the decapsulated packet is forwarded to the oif 1190 list of that entry, else 1192 4 The packet is dropped, and a Register-stop is 1193 triggered towards the source of the Register. 1195 The (S,G) Entry-timer is restarted by Registers arriving 1196 from that source to that group. 1198 2 If the matching (S,G) or (*,G) state contains a null oif 1199 list, the RP unicasts a Register-Stop message to the source 1200 of the Register message; in the latter case, the source- 1201 address field, within the Register-Stop message, is set to 1202 the wildcard value (all 0's). This message is not processed 1203 by intermediate routers, hence no (S,G) state is 1204 constructed between the RP and the source. 1206 3 If the Register message arrival rate warrants it and there 1207 is no existing (S,G) entry, the RP sets up a (S,G) route 1208 entry with the outgoing interface list, excluding iif(S,G), 1209 copied from the (*,G) outgoing interface list, its SPT-bit 1210 is initialized to 0. If a (*,G) entry does not exist, but 1211 there exists a (*,*,RP) entry with the RP corresponding to 1212 G , the oif list for (S,G) is copied -excluding the iif- 1213 from that (*,*,RP) entry. 1215 A timer (Entry-timer) is set for the (S,G) entry and this 1216 timer is restarted by receipt of data packets for (S,G). 1217 The (S,G) entry causes the RP to send a Join/Prune message 1218 for the indicated group towards the source of the register 1219 message. 1221 If the (S,G) oif list becomes null, Join/Prune messages 1222 will not be sent towards the source, S. 1224 3.4 Multicast Data Packet Forwarding 1226 Processing a multicast data packet involves the following steps: 1228 1 Lookup route state based on a longest match of the source 1229 address, and an exact match of the destination address in 1230 the data packet. If neither S, nor G, find a longest match 1231 entry, and the RP for the packet's destination group 1232 address has a corresponding (*,*,RP) entry, then the 1233 longest match does not require an exact match on the 1234 destination group address. In summary, the longest match is 1235 performed in the following order: (1) (S,G), (2) (*,G). If 1236 neither is matched, then a lookup is performed on (*,*,RP) 1237 entries. 1239 2 If the packet arrived on the interface found in the 1240 matching-entry's iif field, and the oif list is not 1241 null: 1243 1 Forward the packet to the oif list for that entry, 1244 excluding the subnet containing S, and restart the 1245 Entry-timer if the matching entry is (S,G). 1246 Optionally, the (S,G) Entry-timer may be restarted by 1247 periodic checking of the matching packet count. 1249 2 If the entry is a (S,G) entry with a cleared SPT-bit, 1250 and a (*,G) or associated (*,*,RP) also exists whose 1251 incoming interface is different than that for (S,G), 1252 set the SPT-bit for the (S,G) entry and trigger an 1253 (S,G) RPT-bit prune towards the RP. 1255 3 If the source of the packet is a directly-connected 1256 host and the router is the DR on the receiving 1257 interface, check the Register-Suppression-timer 1258 associated with the (S,G) entry. If it is not running, 1259 then the router encapsulates the data packet in a 1260 register message and sends it to the RP. 1262 This covers the common case of a packet arriving on the RPF 1263 interface to the source or RP and being forwarded to all 1264 joined branches. It also detects when packets arrive on the 1265 SP-tree, and triggers their pruning from the RP-tree. If it 1266 is the DR for the source, it sends data packets 1267 encapsulated in Registers to the RPs. 1269 3 If the packet matches to an entry but did not arrive on the 1270 interface found in the entry's iif field, check the 1271 SPT-bit of the entry. If the SPT-bit is set, drop the 1272 packet. If the SPT-bit is cleared, then lookup the (*,G), 1273 or (*,*,RP), entry for G. If the packet arrived on the 1274 iif found in (*,G), or the corresponding (*,*,RP), 1275 forward the packet to the oif list of the matching 1276 entry. This covers the case when a data packet matches on a 1277 (S,G) entry for which the SP-tree has not yet been 1278 completely established upstream. 1280 4 If the packet does not match any entry, but the source of 1281 the data packet is a local, directly-connected host, and 1282 the router is the DR on a multi-access LAN and has RP-Set 1283 information, the DR uses the hash function to determine the 1284 RP associated with the destination group, G. The DR creates 1285 a (S,G) entry, with the Register-Suppression-timer not 1286 running, encapsulates the data packet in a Register message 1287 and unicasts it to the RP. 1289 5 If the packet does not match to any entry, and it is not a 1290 local host or the router is not the DR, drop the packet. 1292 3.4.1 Data triggered switch to shortest path tree (SP-tree) 1294 Different criteria can be applied to trigger switching over from 1295 the RP-based shared tree to source-specific, shortest path 1296 trees. 1298 One proposed example is to do so based on data rate. For 1299 example, when a (*,G), or corresponding (*,*,RP), entry is 1300 created, a data rate counter may be initiated at the last-hop 1301 routers. The counter is incremented with every data packet 1302 received for directly connected members of an SM group, if the 1303 longest match is (*,G) or (*,*,RP). If and when the data rate 1304 for the group exceeds a certain configured threshold (t1), the 1305 router initiates `source-specific' data rate counters for the 1306 following data packets. Then, each counter for a source, is 1307 incremented when packets matching on (*,G), or (*,*,RP), are 1308 received from that source. If the data rate from the particular 1309 source exceeds a configured threshold (t2), a (S,G) entry is 1310 created and a Join/Prune message is sent towards the source. If 1311 the RPF interface for (S,G) is 1312 not the same as that for (*,G) -or (*,*,RP), then the SPT-bit 1313 is cleared in the (S,G) entry. 1315 Other configured rules may be enforced to cause or prevent 1316 establishment of (S,G) state. 1318 3.5 Assert 1320 Asserts are used to resolve which of the parallel routers 1321 connected to a multi-access LAN is responsible for forwarding 1322 packets onto the LAN. 1324 3.5.1 Sending Asserts 1326 The following Assert rules are provided when a multicast packet 1327 is received on an outgoing multi-access interface ``I'' of an 1328 existing active (S,G), (*,G) or (*,*,RP) entry: 1330 1 Do unicast routing table lookup on source address from data 1331 packet, and send assert on interface ``I'' for source 1332 address in data packet; include metric preference of 1333 routing protocol and metric from routing table lookup. 1335 2 If route is not found, use metric preference of 0x7fffffff 1336 and metric 0xffffffff. 1338 When an assert is sent for a (*,G) entry, the first bit in the 1339 metric preference (the RPT-bit) is set to 1, indicating the data 1340 packet is routed down the RP-tree. 1342 Asserts should be rate-limited in an implementation-specific 1343 manner. 1345 3.5.2 Receiving Asserts 1347 When an Assert is received the router performs a longest match 1348 on the source and group address in the Assert message, only 1349 active entries -- that have packet forwarding state -- are 1350 matched. The router checks the first bit of the metric 1351 preference (RPT-bit). 1353 1 If the RPT-bit is set, the router first does a match on 1354 (*,G), or (*,*,RP), entries; if no matching entry is found, 1355 it ignores the Assert. 1357 2 If the RPT-bit is not set in the Assert, the router first 1358 does a match on (S,G) entries; if no matching entry is 1359 found, the router matches (*,G) or (*,*,RP) entries. 1361 Receiving Asserts on an entry's outgoing interface: 1363 If the interface that received the Assert message is in the 1364 oif list of the matched entry, then this Assert is processed 1365 by this router as follows: 1367 1 If the Assert's RPT-bit is set and the matching entry is 1368 (*,*,RP), the router creates a (*,G) entry. If the Assert's 1369 RPT-bit is cleared and the matching entry is (*,G), or 1370 (*,*,RP), the router creates a (S,G)RPT-bit entry. 1371 Otherwise, no new entry is created in response to the 1372 Assert. 1374 2 The router then compares the metric values received in the 1375 Assert with the metric values associated with the matched 1376 entry. The RPT-bit and metric preference (in that order) 1377 are treated as the high-order part of an Assert metric 1378 comparison. If the value in the Assert is less than the 1379 router's value (with ties broken by the IP address, where 1380 higher network layer address wins), delete the interface 1381 from the entry. When the deletion occurs for a (*,G) or 1382 (*,*,RP) entry , the interface is also deleted from any 1383 associated (S,G)RPT-bit or (*,G) entries, respectively. The 1384 Entry-timer for the affected entries is restarted. 1386 3 If the router has won the election the router keeps the 1387 interface in its outgoing interface list. It acts as the 1388 forwarder for the LAN. 1390 The winning router sends an Assert message containing its own 1391 metric to that outgoing interface. This will cause other routers 1392 on the LAN to prune that interface from their route entries. The 1393 winning router sets the RPT-bit in the Assert message if a (*,G) 1394 or (S,G)RPT-bit entry was matched. 1396 Receiving Asserts on an entry's incoming interface 1398 If the Assert arrived on the incoming interface of an existing 1399 (S,G), (*,G), or (*,*,RP) entry, the Assert is processed as 1400 follows. If the Assert message does not match the entry, 1401 exactly, it is ignored; i.e, longest-match is not used in this 1402 case. If the Assert message does match exactly, then: 1404 1 Downstream routers will select the upstream router with the 1405 smallest metric preference and metric as their RPF 1406 neighbor. If two metrics are the same, the highest network 1407 layer address is chosen to break the tie. This is important 1408 so that downstream routers send subsequent Joins/Prunes (in 1409 SM) to the correct neighbor. An Assert-timer is initiated 1410 when changing the RPF neighbor to the Assert winner. When 1411 the timer expires, the router resets its RPF neighbor 1412 according to its unicast routing tables to capture network 1413 dynamics and router failures. 1415 2 If the downstream routers have downstream members, and if 1416 the Assert caused the RPF neighbor to change, the 1417 downstream routers must trigger a Join/Prune message to 1418 inform the upstream router that packets are to be forwarded 1419 on the multi-access network. 1421 3.6 Candidate-RP-Advertisements and Bootstrap messages 1423 Candidate-RP-Advertisements (C-RP-Advs) are periodic PIM 1424 messages unicast to the BSR by those routers that are configured 1425 as Candidate-RPs (C-RPs). 1427 Bootstrap messages are periodic PIM messages originated by the 1428 Bootstrap router (BSR) within a domain, and forwarded hop-by-hop 1429 to distribute the current RP-set to all routers in that domain. 1431 The Bootstrap messages also support a simple mechanism by which 1432 the Candidate BSR (C-BSR) with the highest BSR-priority and 1433 address (referred to as the preferred BSR) is elected as the BSR 1434 for the domain. We recommend that each router configured as a 1435 C-RP also be configured as a C-BSR. Sections 3.6.2 and 3.6.3 1436 describe the combined function of Bootstrap messages as the 1437 vehicle for BSR election and RP-Set distribution. 1439 A Finite State Machine description of the BSR election and RP- 1440 Set distribution mechanisms is included in Appendix II. 1442 3.6.1 Sending Candidate-RP-Advertisements 1444 C-RPs periodically unicast C-RP-Advs to the BSR for that domain. 1445 The interval for sending these messages is subject to local 1446 configuration at the C-RP. 1448 Candidate-RP-Advertisements carry group address and group mask 1449 fields. This enables the advertising router to limit the 1450 advertisement to certain prefixes or scopes of groups. The 1451 advertising router may enforce this scope acceptance when 1452 receiving Registers or Join/Prune messages. C-RPs should send 1453 C-RP-Adv messages with the `Priority' field set to `0'. 1455 3.6.2 Receiving C-RP-Advs and Originating Bootstrap 1457 Upon receiving a C-RP-Adv, a router does the following: 1459 1 If the router is not the elected BSR, it ignores the 1460 message, else 1462 2 The BSR adds the RP address to its local pool of candidate 1463 RPs, according to the associated group prefix(es) in the 1464 C-RP-Adv message. The Holdtime in the C-RP-Adv message is 1465 also stored with the corresponding RP, to be included later 1466 in the Bootstrap message. The BSR may apply a local policy 1467 to limit the number of Candidate RPs included in the 1468 Bootstrap message. The BSR may override the prefix 1469 indicated in a C-RP-Adv unless the `Priority' field is not 1470 zero. 1472 The BSR keeps an RP-timer per RP in its local RP-set. The RP- 1473 timer is initialized to the Holdtime in the RP's C-RP-Adv. When 1474 the timer expires, the corresponding RP is removed from the RP- 1475 set. The RP-timer is restarted by the C-RP-Advs from the 1476 corresponding RP. 1478 The BSR also uses its Bootstrap-timer to periodically send 1479 Bootstrap messages. In particular, when the Bootstrap-timer 1480 expires, the BSR originates a Bootstrap message on each of its 1481 PIM interfaces. To reduce the bootstrap message overhead during 1482 partition healing, the BSR should set a random time (as a 1483 function of the priority and address) after which the Bootstrap 1484 message is originated only if no other preferred Bootstrap 1485 message is received. For details see appendix 1486 6.2. The message is sent with a TTL of 1 to the `ALL-PIM- 1487 ROUTERS' group. In steady state, the BSR originates Bootstrap 1488 messages periodically. At startup, the Bootstrap-timer is 1489 initialized to [Bootstrap-Timeout], causing the first Bootstrap 1490 message to be originated only when and if the timer expires. For 1491 timer details, see Section 3.6.3. A DR unicasts a Bootstrap 1492 message to each new PIM neighbor, i.e., after the DR receives 1493 the neighbor's Hello message (it does so even if the new 1494 neighbor becomes the DR). 1496 The Bootstrap message is subdivided into sets of group- 1497 prefix,RP-Count,RP-addresses. For each RP-address, the 1498 corresponding Holdtime is included in the ``RP-Holdtime" field. 1499 The format of the Bootstrap message allows `semantic 1500 fragmentation', if the length of the original Bootstrap message 1501 exceeds the packet maximum boundaries (see Section 4). However, 1502 we recommend against configuring a large number of routers as 1503 C-RPs, to reduce the semantic fragmentation required. 1505 3.6.3 Receiving and Forwarding Bootstrap 1507 Each router keeps a Bootstrap-timer, initialized to [Bootstrap- 1508 Timeout] at startup. 1510 When a router receives Bootstrap message sent to `ALL-PIM- 1511 ROUTERS' group, it performs the following: 1513 1 If the message was not sent by the RPF neighbor towards the 1514 BSR address included, the message is dropped. Else 1516 2 If the included BSR is not preferred over, and not equal 1517 to, the currently active BSR: 1519 1 If the Bootstrap-timer has not yet expired, or if the 1520 receiving router is a C-BSR, then the Bootstrap 1521 message is dropped. Else 1523 2 If the Bootstrap-timer has expired and the receiving 1524 router is not a C-BSR, the receiving router stores the 1525 RP-Set and BSR address and priority found in the 1526 message, and restarts the timer by setting it to 1527 [Bootstrap-Timeout]. The Bootstrap message is then 1528 forwarded out all PIM interfaces, excluding the one 1529 over which the message arrived, to `ALL-PIM-ROUTERS' 1530 group, with a TTL of 1. 1532 3 If the Bootstrap message includes a BSR address that is 1533 preferred over, or equal to, the currently active BSR, the 1534 router restarts its Bootstrap-timer at [Bootstrap-Timeout] 1535 seconds. and stores the BSR address and RP-Set information. 1537 The Bootstrap message is then forwarded out all PIM 1538 interfaces, excluding the one over which the message 1539 arrived, to `ALL-PIM-ROUTERS' group, with a TTL of 1. 1541 4 If the receiving router has no current RP set information 1542 and the Bootstrap was unicast to it from a directly 1543 connected neighbor, the router stores the information as 1544 its new RP-set. This covers the startup condition when a 1545 newly booted router obtains the RP-Set and BSR address from 1546 its DR. 1548 When a router receives a new RP-Set, it checks if each of the 1549 RPs referred to by existing state (i.e., by (*,G), (*,*,RP), or 1550 (S,G)RPT-bit entries) is in the new RP-Set. If an RP is not in 1551 the new RP-set, that RP is considered unreachable and the hash 1552 algorithm (see below) is re-performed for each group with 1553 locally active state that previously hashed to that RP. This 1554 will cause those groups to be distributed among the remaining 1555 RPs. When the new RP-Set contains a new RP, the value of the new 1556 RP is calculated for each group covered by that C-RP's Group- 1557 prefix. Any group for which the new RP's value is greater than 1558 the previously active RP's value is switched over to the new RP. 1560 3.7 Hash Function 1562 The hash function is used by all routers within a domain, to map 1563 a group to one of the C-RPs from the RP-Set. For a particular 1564 group, G, the hash function uses only those C-RPs whose Group- 1565 prefix covers G. The algorithm takes as input the group address, 1566 and the addresses of the Candidate RPs, and gives as output one 1567 RP address to be used. 1569 The protocol requires that all routers hash to the same RP 1570 within a domain (except for transients). The following hash 1571 function must be used in each router: 1573 1 For RP addresses in the RP-Set, whose Group-prefix covers 1574 G, select the RPs with the highest priority (i.e. lowest 1575 `Priority' value), and compute a value: 1577 Value(G,M,C(i))= 1578 (1103515245 * ((1103515245 * (G&M)+12345) XOR C(i)) + 12345) mod 2^31 1580 where C_i is the RP address and M is a hash-mask 1581 included in Bootstrap messages. The hash-mask allows a 1582 small number of consecutive groups (e.g., 4) to always hash 1583 to the same RP. For instance, hierarchically-encoded data 1584 can be sent on consecutive group addresses to get the same 1585 delay and fate-sharing characteristics. 1587 For address families other than IPv4, a 32-bit digest to be 1588 used as C_i must first be derived from the actual RP 1589 address. Such a digest method must be used consistently 1590 throughout the PIM domain. For IPv6 addresses, we recommend 1591 using the equivalent IPv4 address for an IPv4-compatible 1592 address, and the CRC-32 checksum [7] of all other IPv6 1593 addresses. 1595 2 From the RPs with the highest priority (i.e. lowest 1596 `Priority' value), the candidate with the highest resulting 1597 value is then chosen as the RP for that group, and its 1598 identity and hash value are stored with the entry created. 1600 Ties between RPs having the same hash value and priority, 1601 are broken in advantage of the highest address. 1603 The hash function algorithm is invoked by a DR, upon reception 1604 of a packet, or IGMP membership indication, for a group, for 1605 which the DR has no entry. It is invoked by any router that has 1606 (*,*,RP) state when a packet is received for which there is no 1607 corresponding (S,G) or (*,G) entry. Furthermore, the hash 1608 function is invoked by all routers upon receiving a (*,G) or 1609 (*,*,RP) Join/Prune message. 1611 3.8 Processing Timer Events 1613 In this subsection, we enumerate all timers that have been 1614 discussed or implied. Since some critical timer events are not 1615 associated with the receipt or sending of messages, they are not 1616 fully covered by earlier subsections. 1618 Timers are implemented in an implementation-specific manner. For 1619 example, a timer may count up or down, or may simply expire at a 1620 specific time. Setting a timer to a value T means that it will 1621 expire after T seconds. 1623 3.8.1 Timers related to tree maintenance 1625 Each (S,G), (*,G), and (*,*,RP) route entry has multiple timers 1626 associated with it: one for each interface in the outgoing 1627 interface list, one for the multicast routing entry itself, and 1628 one optional Join/Prune-Suppression-Timer. Each (S,G) and (*,G) 1629 entry also has an Assert-timer and a Random-Delay-Join-Timer for 1630 use with Asserts. In addition, DR's have a Register- 1631 Suppression-timer for each (S,G) entry and every router has a 1632 single Join/Prune-timer. (A router may optionally keep separate 1633 Join/Prune-timers for different interfaces or route entries if 1634 different Join/Prune periods are desired.) 1636 * [Join/Prune-Timer] This timer is used for periodically 1637 sending aggregate Join/Prune messages. To avoid 1638 synchronization among routers booting simultaneously, it is 1639 initially set to a random value between 1 and [Join/Prune- 1640 Period]. When it expires, the timer is immediately 1641 restarted to [Join/Prune-Period]. A Join/Prune message is 1642 then sent out each interface. This timer should not be 1643 restarted by other events. 1645 * [Join/Prune-Suppression-Timer (kept per route entry)] A 1646 route entry's (optional) Join/Prune-Suppression-Timer may 1647 be used to suppress duplicate joins from multiple 1648 downstream routers on the same LAN. When a Join message is 1649 received from a neighbor on the entry's incoming interface 1650 in which the included Holdtime is higher than the router's 1651 own [Join/Prune-Holdtime] (with ties broken by higher 1652 network layer address), the timer is set to [Join/Prune- 1653 Suppression-Timeout], with some random jitter introduced to 1654 avoid synchronization of triggered Join/Prune messages on 1655 expiration. (The random timeout value must be < 1.5 * 1656 [Join/Prune-Period] to prevent losing data after 2 dropped 1657 Join/Prunes.) The timer is restarted every time a 1658 subsequent Join/Prune message (with higher Holdtime/IP 1659 address) for the entry is received on its incoming 1660 interface. While the timer is running, Join/Prune messages 1661 for the entry are not sent. This timer is idle (not 1662 running) for point-to-point links. 1664 * [Oif-Timer (kept per oif for each route entry)] A timer for 1665 each oif of a route entry is used to time out that oif. 1666 Because some of the outgoing interfaces in an (S,G) entry 1667 are copied from the (*,G) outgoing interface list, they may 1668 not have explicit (S,G) join messages from some of the 1669 downstream routers (i.e., where members are joining to the 1670 (*,G) tree only). Thus, when an Oif-timer is restarted in a 1671 (*,G) entry, the Oif-timer is restarted for that interface 1672 in each existing (S,G) entry whose oif list contains that 1673 interface. The same rule applies to (*,G) and (S,G) entries 1674 when restarting an Oif-timer on a (*,*,RP) entry. 1676 The following table shows its usage when first adding the 1677 oif to the entry's oiflist, when it should be restarted 1678 (unless it is already higher), and when it should be 1679 decreased (unless it is already lower). 1681 Set to | When | Applies to 1682 included Holdtime | adding oif off Join/Prune | (S,G) (*,G) (*,*,RP) 1684 Increased (only) to | When | Applies to 1685 included Holdtime | received Join/Prune | (S,G) (*,G) (*,*,RP) 1686 (*,*,RP) oif-timer value | (*,*,RP) oif-timer restarted | (S,G) (*,G) 1687 (*,G) oif-timer value | (*,G) oif-timer restarted | (S,G) 1689 When the timer expires, the oif is removed from the oiflist 1690 if there are no directly-connected members. When deleted, 1691 the oif is also removed in any associated (S,G) or (*,G) 1692 entries. 1694 * [Entry-Timer (kept per route entry)] A timer for each route 1695 entry is used to time out that entry. The following table 1696 summarizes its usage when first adding the oif to the 1697 entry's oiflist, and when it should be restarted (unless it 1698 is already higher). 1700 Set to | When | Applies to 1701 [Data- Timeout] | created off data packet | (S,G) 1702 included Holdtime | created off Join/Prune | (S,G) (*,G) (*,*,RP) 1704 Increased (only) to | When | Applies to 1705 [Data-Timeout] | receiving data packets | (S,G)no RPT-bit 1706 oif-timer value | any oif-timer restarted | (S,G)RPT-bit (*,G) (*,*,RP) 1707 [Assert-Timeout] | assert received | (S,G)RPT-bit (*,G) w/null oif 1709 When the timer expires, the route entry is deleted; if the 1710 entry is a (*,G) or (*,*,RP) entry, all associated 1711 (S,G)RPT-bit entries are also deleted. 1713 * [Register-Suppression-Timer (kept per (S,G) route entry)] 1714 An (S,G) route entry's Register-Suppression-Timer is used 1715 to suppress registers when the RP is receiving data packets 1716 natively. When a Register-Stop message for the entry is 1717 received from the RP, the timer is set to a random value in 1718 the range 0.5 * [Register-Suppression-Timeout] to 1.5 * 1719 [Register-Suppression-Timeout]. While the timer is running, 1720 Registers for that entry will be suppressed. If null 1721 registers are used, a null register is sent [Probe-Time] 1722 seconds before the timer expires. 1724 * [Assert-Timer (per (S,G) or (*,G) route entry)] The 1725 Assert-Timer for an (S,G) or (*,G) route entry is used for 1726 timing out Asserts received. When an Assert is received and 1727 the RPF neighbor is changed to the Assert winner, the 1728 Assert-Timer is set to [Assert-Timeout], and is restarted 1729 to this value every time a subsequent Assert for the entry 1730 is received on its incoming interface. When the timer 1731 expires, the router resets its RPF neighbor according to 1732 its unicast routing table. 1734 * [Random-Delay-Join-Timer (per (S,G) or (*,G) route entry)] 1735 The Random-Delay-Join-Timer for an (S,G) or (*,G) route 1736 entry is used to prevent synchronization among downstream 1737 routers on a LAN when their RPF neighbor changes. When the 1738 RPF neighbor changes, this timer is set to a random value 1739 between 0 and [Random-Delay-Join-Timeout] seconds. When the 1740 timer expires, a triggered Join/Prune message is sent for 1741 the entry unless its Join/Prune-Suppression-Timer is 1742 running. 1744 3.8.2 Timers relating to neighbor discovery 1746 * [Hello-Timer] This timer is used to periodically send Hello 1747 messages. To avoid synchronization among routers booting 1748 simultaneously, it is initially set to a random value 1749 between 1 and [Hello-Period]. When it expires, the timer is 1750 immediately restarted to [Hello-Period]. A Hello message is 1751 then sent out each interface. This timer should not be 1752 restarted by other events. 1754 * [Neighbor-Timer (kept per neighbor)] A Neighbor-Timer for 1755 each neighbor is used to time out the neighbor state. When 1756 a Hello message is received from a new neighbor, the timer 1757 is initially set to the Holdtime included in the Hello 1758 message (which is equal to the neighbor's value of [Hello- 1759 Holdtime]). Every time a subsequent Hello is received from 1760 that neighbor, the timer is restarted to the Holdtime in 1761 the Hello. When the timer expires, the neighbor state is 1762 removed. 1764 3.8.3 Timers relating to RP information 1766 * [C-RP-Adv-Timer (C-RP's only)] Routers configured as 1767 candidate RP's use this timer to periodically send C-RP-Adv 1768 messages. To avoid synchronization among routers booting 1769 simultaneously, the timer is initially set to a random 1770 value between 1 and [C-RP-Adv-Period]. When it expires, the 1771 timer is immediately restarted to [C-RP-Adv-Period]. A C- 1772 RP-Adv message is then sent to the elected BSR. This timer 1773 should not be restarted by other events. 1775 * [RP-Timer (BSR only, kept per RP in RP-Set)] The BSR uses a 1776 timer per RP in the RP-Set to monitor liveness. When a C-RP 1777 is added to the RP-Set, its timer is set to the Holdtime 1778 included in the C-RP-Adv message from that C-RP (which is 1779 equal to the C-RP's value of [RP-Holdtime]). Every time a 1780 subsequent C-RP-Adv is received from that RP, its timer is 1781 restarted to the Holdtime in the C-RP-Adv. When the timer 1782 expires, the RP is removed from the RP-Set included in 1783 Bootstrap messages. 1785 * [Bootstrap-Timer] This timer is used by the BSR to 1786 periodically originate Bootstrap messages, and by other 1787 routers to time out the BSR (see 1788 3.6.3). This timer is initially set to [Bootstrap- 1789 Timeout]. A C-BSR restarts this timer to [Bootstrap- 1790 Timeout] upon receiving a Bootstrap message from a 1791 preferred router, and originates a Bootstrap message and 1792 restarts the timer to [Bootstrap-Period] when it expires. 1793 Routers not configured as C-BSR's restart this timer to 1794 [Bootstrap-Timeout] upon receiving a Bootstrap message from 1795 the elected or a more preferred BSR, and ignore Bootstrap 1796 messages from non-preferred C-BSRs while it is running. 1798 3.8.4 Default timer values 1800 Most of the default timeout values for state information are 3.5 1801 times the refresh period. For example, Hellos refresh Neighbor 1802 state and the default Hello-timer period is 30 seconds, so a 1803 default Neighbor-timer duration of 105 seconds is included in 1804 the Holdtime field of the Hellos. In order to improve 1805 convergence, however, the default timeout value for information 1806 related to RP liveness and Bootstrap messages is 2.5 times the 1807 refresh period. 1809 In this version of the spec, we suggest particular numerical 1810 timer settings. A future version of the specification will 1811 specify a mechanism for timer values to be scaled based upon 1812 observed network parameters. 1814 * [Join/Prune-Period] This is the interval between 1815 sending Join/Prune messages. Default: 60 seconds. This 1816 value may be set to take into account such things as the 1817 configured bandwidth and expected average number of 1818 multicast route entries for the attached network or link 1819 (e.g., the period would be longer for lower-speed links, or 1820 for routers in the center of the network that expect to 1821 have a larger number of entries ). In addition, a router 1822 could modify this value (and corresponding Join/Prune- 1823 Holdtime value) if the number of route entries changes 1824 significantly (e.g., by an order of magnitude). For 1825 example, given a default minimum Join/Prune-Period value, 1826 if the number of route entries with a particular iif 1827 increases from N to N*100, the router could increase its 1828 Join/Prune-Period (and Join/Prune-Holdtime), for that 1829 interface, by a factor of 10; and if/when the number of 1830 entries decreases back to N, the Join/Prune-Period (and 1831 Join/Prune-Holdtime) could be decreased to its previous 1832 value. If the Join/Prune-Period is modified, these changes 1833 should be made relatively infrequently and the router 1834 should continue to refresh at its previous Join/Prune- 1835 Period for at least Join/Prune-Holdtime, in order to allow 1836 the upstream router to adapt. 1838 * [Join-Prune Holdtime] This is the Holdtime specified in 1839 Join/Prune messages, and is used to time out oifs. This 1840 should be set to 3.5 * [Join/Prune-Period]. Default: 210 1841 seconds. 1843 * [Join/Prune-Suppression-Timeout] This is the mean 1844 interval between receiving a Join/Prune with a higher 1845 Holdtime (with ties broken by higher network layer address) 1846 and allowing duplicate Join/Prunes to be sent again. This 1847 should be set to approximately 1.25 * [Join/Prune-Period]. 1848 Default: 75 seconds. 1850 * [Data-Timeout] This is the time after which (S,G) state 1851 for a silent source will be deleted. Default: 210 1852 seconds. 1854 * [Register-Suppression-Timeout] This is the mean 1855 interval between receiving a Register-Stop and allowing 1856 Registers to be sent again. A lower value means more 1857 frequent register bursts at RP, while a higher value means 1858 longer join latency for new receivers. Default: 60 1859 seconds. (Note that if null Registers are sent [Probe- 1860 Time] seconds before the timeout, register bursts are 1861 prevents, and [Register-Suppression-Timeout] may be lowered 1862 to decrease join latency.) 1863 * [Probe-Time] When null Registers are used, this is the 1864 time between sending a null Register and the Register- 1865 Suppression-Timer expiring unless it is restarted by 1866 receiving a Register-Stop. Thus, a null Register would be 1867 sent when the Register-Suppression-Timer reaches this 1868 value. Default: 5 seconds. 1870 * [Assert-Timeout] This is the interval between the last 1871 time an Assert is received, and the time at which the 1872 assert is timed out. Default: 180 seconds. 1874 * [Random-Delay-Join-Timeout] This is the maximum 1875 interval between the time when the RPF neighbor changes, 1876 and the time at which a triggered Join/Prune message is 1877 sent. Default: 4.5 seconds. 1879 * [Hello-Period] This is the interval between sending 1880 Hello messages. Default: 30 seconds. 1882 * [Hello-Holdtime] This is the Holdtime specified in 1883 Hello messages, after which neighbors will time out their 1884 neighbor entries for the router. This should be set to 3.5 1885 * [Hello-Period]. Default: 105 seconds. 1887 * [C-RP-Adv-Period] For C-RPs, this is the interval 1888 between sending C-RP-Adv messages. Default: 60 seconds. 1890 * [RP-Holdtime] For C-RPs, this is the Holdtime specified 1891 in C-RP-Adv messages, and is used by the BSR to time out 1892 RPs. This should be set to 2.5 * [C-RP-Adv-Period]. 1893 Default: 150 seconds. 1895 * [Bootstrap-Period] At the elected BSR, this is the 1896 interval between originating Bootstrap messages, and should 1897 be equal to 60 seconds. 1899 * [Bootstrap-Timeout] This is the time after which the 1900 elected BSR will be assumed unreachable when Bootstrap 1901 messages are not received from it. This should be set to 1902 `2 * [Bootstrap-Period] + 10'. Default: 130 seconds. 1904 3.9 Summary of flags used 1906 Following is a summary of all the flags used in our scheme. 1908 Bit | Used in | Definition 1910 Border | Register | Register for external sources is coming from 1911 PIM multicast border router 1912 Null | Register | Register sent as Probe of RP, the encapsulated 1913 IP data packet should not be forwarded 1914 RPT | Route entry | Entry represents state on the RP-tree 1915 RPT | Join/Prune | Join is associated with the shared tree and 1916 therefore the Join/Prune message is propagated 1917 along the RP-tree (source encoded is an RP 1918 address) 1919 RPT | Assert | The data packet was routed down the shared 1920 tree; thus, the path indicated corresponds 1921 to the RP tree 1922 SPT | (S,G) entry | Packets have arrived on the iif towards S, and 1923 the iif is different from the (*,G) iif 1924 WC |Join | The receiver expects to receive packets from all 1925 sources via this (shared tree) path. Thus, the 1926 Join/Prune applies to a (*,G) entry 1927 WC | Route entry | Wildcard entry; if there is no more specific 1928 match for a particular source, packets will 1929 be forwarded according to this entry 1931 3.10 Security 1933 All PIM control messages may use IPsec [6] to address security 1934 concerns. 1936 4 Packet Formats 1938 This section describes the details of the packet formats for PIM 1939 control messages. 1941 All PIM control messages have protocol number 103. 1943 Basically, PIM messages are either unicast (e.g. Registers and 1944 Register-Stop), or multicast hop-by-hop to `ALL-PIM-ROUTERS' 1945 group `224.0.0.13' (e.g. Join/Prune, Asserts, etc.). 1947 0 1 2 3 1948 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 1949 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1950 |PIM Ver| Type | Reserved | Checksum | 1951 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1953 PIM Ver 1954 PIM Version number is 2. 1956 Type Types for specific PIM messages. PIM Types are: 1958 0 = Hello 1959 1 = Register 1960 2 = Register-Stop 1961 3 = Join/Prune 1962 4 = Bootstrap 1963 5 = Assert 1964 6 = Graft (used in PIM-DM only) 1965 7 = Graft-Ack (used in PIM-DM only) 1966 8 = Candidate-RP-Advertisement 1968 Reserved 1969 set to zero. Ignored upon receipt. 1971 Checksum 1972 The checksum is the 16-bit one's complement of the one's 1973 complement sum of the entire PIM message, (excluding the 1974 data portion in the Register message). For computing the 1975 checksum, the checksum field is zeroed. 1977 4.1 Encoded Source and Group Address formats 1979 1 Encoded-Unicast-address: Takes the following format: 1981 0 1 2 3 1982 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 1983 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1984 | Addr Family | Encoding Type | Unicast Address | 1985 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+++++++ 1987 Addr Family 1988 The address family of the `Unicast Address' field of 1989 this address. 1991 Here is the address family numbers assigned by IANA: 1993 Number Description 1994 - ------ --------------------------------------------------------- 1995 0 Reserved 1996 1 IP (IP version 4) 1997 2 IP6 (IP version 6) 1998 3 NSAP 1999 4 HDLC (8-bit multidrop) 2000 5 BBN 1822 2001 6 802 (includes all 802 media plus Ethernet "canonical format") 2002 7 E.163 2003 8 E.164 (SMDS, Frame Relay, ATM) 2004 9 F.69 (Telex) 2005 10 X.121 (X.25, Frame Relay) 2006 11 IPX 2007 12 Appletalk 2008 13 Decnet IV 2009 14 Banyan Vines 2010 15 E.164 with NSAP format subaddress 2012 Encoding Type 2013 The type of encoding used within a specific Address 2014 Family. The value `0' is reserved for this field, and 2015 represents the native encoding of the Address Family. 2017 Unicast Address 2018 The unicast address as represented by the given 2019 Address Family and Encoding Type. 2021 2 Encoded-Group-Address: Takes the following format: 2023 0 1 2 3 2024 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 2025 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2026 | Addr Family | Encoding Type | Reserved | Mask Len | 2027 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2028 | Group multicast Address | 2029 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2031 Addr Family 2032 described above. 2034 Encoding Type 2035 described above. 2037 Reserved 2038 Transmitted as zero. Ignored upon receipt. 2040 Mask Len 2041 The Mask length is 8 bits. The value is the number of 2042 contiguous bits left justified used as a mask which 2043 describes the address. It is less than or equal to the 2044 address length in bits for the given Address Family 2045 and Encoding Type. If the message is sent for a single 2046 group then the Mask length must equal the address 2047 length in bits for the given Address Family and 2048 Encoding Type. (e.g. 32 for IPv4 native encoding and 2049 128 for IPv6 native encoding). 2051 Group multicast Address 2052 contains the group address. 2054 3 Encoded-Source-Address: Takes the following format: 2056 0 1 2 3 2057 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 2058 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2059 | Addr Family | Encoding Type | Rsrvd |S|W|R| Mask Len | 2060 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2061 | Source Address | 2062 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2064 Addr Family 2065 described above. 2067 Encoding Type 2068 described above. 2070 Reserved 2071 Transmitted as zero, ignored on receipt. 2073 S,W,R See Section 4.5 for details. 2075 Mask Length 2076 Mask length is 8 bits. The value is the number of 2077 contiguous bits left justified used as a mask which 2078 describes the address. The mask length must be less 2079 than or equal to the address length in bits for the 2080 given Address Family and Encoding Type. If the message 2081 is sent for a single group then the Mask length must 2082 equal the address length in bits for the given Address 2083 Family and Encoding Type. In version 2 of PIM, it is 2084 strongly recommended that this field be set to 32 for 2085 IPv4 native encoding. 2087 Source Address 2088 The source address. 2090 4.2 Hello Message 2092 It is sent periodically by routers on all interfaces. 2094 0 1 2 3 2095 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 2096 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2097 |PIM Ver| Type | Reserved | Checksum | 2098 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2099 | OptionType | OptionLength | 2100 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2101 | OptionValue | 2102 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+++ 2103 | . | 2104 | . | 2105 | . | 2106 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2107 | OptionType | OptionLength | 2108 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2109 | OptionValue | 2110 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+++ 2112 PIM Version, Type, Reserved, Checksum 2113 Described above. 2115 OptionType 2116 The type of the option given in the following OptionValue 2117 field. 2119 OptionLength 2120 The length of the OptionValue field in bytes. 2122 OptionValue 2123 A variable length field, carrying the value of the option. 2125 The Option fields may contain the following values: 2127 * OptionType = 1; OptionLength = 2; OptionValue = Holdtime; 2128 where Holdtime is the amount of time a receiver must keep 2129 the neighbor reachable, in seconds. If the Holdtime is set 2130 to `0xffff', the receiver of this message never times out 2131 the neighbor. This may be used with ISDN lines, to avoid 2132 keeping the link up with periodic Hello messages. 2134 Furthermore, if the Holdtime is set to `0', the information 2135 is timed out immediately. 2137 * OptionType 2 to 16: reserved 2139 * The rest of the OptionTypes are defined in another 2140 document. 2142 In general, options may be ignored; but a router must not ignore 2143 the 2144 4.3 Register Message 2146 A Register message is sent by the DR or a PMBR to the RP when a 2147 multicast packet needs to be transmitted on the RP-tree. Source 2148 address is set to the address of the DR, destination address is 2149 to the RP's address. 2151 0 1 2 3 2152 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 2153 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2154 |PIM Ver| Type | Reserved | Checksum | 2155 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2156 |B|N| Reserved | 2157 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2158 | | 2159 Multicast data packet 2160 | | 2161 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2163 PIM Version, Type, Reserved, Checksum 2164 Described above. Note that the checksum for Registers 2165 is done only on the PIM header, excluding the data packet 2166 portion. 2168 B The Border bit. If the router is a DR for a source that it 2169 is directly connected to, it sets the B bit to 0. If the 2170 router is a PMBR for a source in a directly connected 2171 cloud, it sets the B bit to 1. 2173 N The Null-Register bit. Set to 1 by a DR that is probing 2174 the RP before expiring its local Register-Suppression 2175 timer. Set to 0 otherwise. 2177 Multicast data packet 2178 The original packet sent by the source. 2180 For (S,G) null Registers, the Multicast data packet portion 2181 contains only a dummy header with S as the source address, G as 2182 the destination address, and a data length of zero. 2184 4.4 Register-Stop Message 2186 A Register-Stop is unicast from the RP to the sender of the 2187 Register message. Source address is the address to which the 2188 register was addressed. Destination address is the source 2189 address of the register message. 2191 0 1 2 3 2192 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 2193 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2194 |PIM Ver| Type | Reserved | Checksum | 2195 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2196 | Encoded-Group Address | 2197 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2198 | Encoded-Unicast-Source Address | 2199 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2201 PIM Version, Type, Reserved, Checksum 2202 Described above. 2204 Encoded-Group Address 2205 Format described above. Note that for Register-Stops the 2206 Mask Len field contains full address length * 8 (e.g. 32 2207 for IPv4 native encoding), if the message is sent for a 2208 single group. 2210 Encoded-Unicast-Source Address 2211 host address of source from multicast data packet in 2212 register. The format for this address is given in the 2213 Encoded-Unicast-Address in 4.1. A special wild card value 2214 (0's), can be used to indicate any source. 2216 4.5 Join/Prune Message 2218 A Join/Prune message is sent by routers towards upstream sources 2219 and RPs. Joins are sent to build shared trees (RP trees) or 2220 source trees (SPT). Prunes are sent to prune source trees when 2221 members leave groups as well as sources that do not use the 2222 shared tree. 2224 0 1 2 3 2225 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 2226 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2227 |PIM Ver| Type | Reserved | Checksum | 2228 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2229 | Encoded-Unicast-Upstream Neighbor Address | 2230 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2231 | Reserved | Num groups | Holdtime | 2232 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2233 | Encoded-Multicast Group Address-1 | 2234 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2235 | Number of Joined Sources | Number of Pruned Sources | 2236 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2237 | Encoded-Joined Source Address-1 | 2238 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2239 | . | 2240 | . | 2241 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2242 | Encoded-Joined Source Address-n | 2243 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2244 | Encoded-Pruned Source Address-1 | 2245 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2246 | . | 2247 | . | 2248 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2249 | Encoded-Pruned Source Address-n | 2250 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2251 | . | 2252 | . | 2253 | . | 2254 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2255 | Encoded-Multicast Group Address-n | 2256 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2257 | Number of Joined Sources | Number of Pruned Sources | 2258 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2259 | Encoded-Joined Source Address-1 | 2260 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2261 | . | 2262 | . | 2263 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2264 | Encoded-Joined Source Address-n | 2265 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2266 | Encoded-Pruned Source Address-1 | 2267 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2268 | . | 2269 | . | 2270 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2271 | Encoded-Pruned Source Address-n | 2272 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2274 PIM Version, Type, Reserved, Checksum 2275 Described above. 2277 Encoded-Unicast Upstream Neighbor Address 2278 The address of the RPF or upstream neighbor. The format 2279 for this address is given in the Encoded-Unicast-Address in 2280 4.1. .IP "Reserved" 2281 Transmitted as zero, ignored on receipt. 2283 Holdtime 2284 The amount of time a receiver must keep the Join/Prune 2285 state alive, in seconds. If the Holdtime is set to 2286 `0xffff', the receiver of this message never times out the 2287 oif. This may be used with ISDN lines, to avoid keeping the 2288 link up with periodical Join/Prune messages. Furthermore, 2289 if the Holdtime is set to `0', the information is timed out 2290 immediately. 2292 Number of Groups 2293 The number of multicast group sets contained in the 2294 message. 2296 Encoded-Multicast group address 2297 For format description see Section 2298 4.1. A wild card group in the (*,*,RP) join is represented 2299 by a 224.0.0.0 in the group address field and `4' in the 2300 mask length field. A (*,*,RP) join also has the WC-bit and 2301 the RPT-bit set. 2303 Number of Joined Sources 2304 Number of join source addresses listed for a given group. 2306 Join Source Address-1 .. n 2307 This list contains the sources that the sending router 2308 will forward multicast datagrams for if received on the 2309 interface this message is sent on. 2311 See format section 4.1. The fields explanation for the 2312 Encoded-Source-Address format follows: 2314 Reserved 2315 Described above. 2317 S The Sparse bit is a 1 bit value, set to 1 for PIM-SM. 2318 It is used for PIM v.1 compatibility. 2320 W The WC bit is a 1 bit value. If 1, the join or prune 2321 applies to the (*,G) or (*,*,RP) entry. If 0, the join 2322 or prune applies to the (S,G) entry where S is Source 2323 Address. Joins and prunes sent towards the RP must 2324 have this bit set. 2326 R The RPT-bit is a 1 bit value. If 1, the information 2327 about (S,G) is sent towards the RP. If 0, the 2328 information must be sent toward S, where S is the 2329 Source Address. 2331 Mask Length, Source Address 2332 Described above. 2334 Represented in the form of 2335 < WC-bit >< RPT-bit >< Source address>: 2337 A source address could be a host IPv4 native encoding 2338 address : 2340 < 0 >< 0 >< 32 >< 192.1.1.17 > 2342 A source address could be the RP's IP address : 2344 < 1 >< 1 >< 32 >< 131.108.13.111 > 2346 A source address could be a subnet address to prune from 2347 the RP-tree : 2349 < 0 >< 1 >< 28 >< 192.1.1.16 > 2351 A source address could be a general aggregate : 2353 < 0 >< 0 >< 16 >< 192.1.0.0 > 2355 Number of Pruned Sources 2356 Number of prune source addresses listed for a group. 2358 Prune Source Address-1 .. n 2359 This list contains the sources that the sending router 2360 does not want to forward multicast datagrams for when 2361 received on the interface this message is sent on. If the 2362 Join/Prune message boundary exceeds the maximum packet 2363 size, then the join and prune lists for the same group must 2364 be included in the same packet. 2366 4.6 Bootstrap Message 2368 The Bootstrap messages are multicast to `ALL-PIM-ROUTERS' group, 2369 out all interfaces having PIM neighbors (excluding the one over 2370 which the message was received). Bootstrap messages are sent 2371 with TTL value of 1. Bootstrap messages originate at the BSR, 2372 and are forwarded by intermediate routers. 2374 Bootstrap message is divided up into `semantic fragments', if 2375 the original message exceeds the maximum packet size boundaries. 2377 The semantics of a single `fragment' is given below: 2379 0 1 2 3 2380 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 2381 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2382 |PIM Ver| Type | Reserved | Checksum | 2383 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2384 | Fragment Tag | Hash Mask len | BSR-priority | 2385 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2386 | Encoded-Unicast-BSR-Address | 2387 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2388 | Encoded-Group Address-1 | 2389 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2390 | RP-Count-1 | Frag RP-Cnt-1 | Reserved | 2391 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2392 | Encoded-Unicast-RP-Address-1 | 2393 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2394 | RP1-Holdtime | RP1-Priority | Reserved | 2395 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2396 | Encoded-Unicast-RP-Address-2 | 2397 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2398 | RP2-Holdtime | RP2-Priority | Reserved | 2399 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2400 | . | 2401 | . | 2402 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2403 | Encoded-Unicast-RP-Address-m | 2404 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2405 | RPm-Holdtime | RPm-Priority | Reserved | 2406 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2407 | Encoded-Group Address-2 | 2408 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2409 | . | 2410 | . | 2411 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2412 | Encoded-Group Address-n | 2413 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2414 | RP-Count-n | Frag RP-Cnt-n | Reserved | 2415 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2416 | Encoded-Unicast-RP-Address-1 | 2417 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2418 | RP1-Holdtime | RP1-Priority | Reserved | 2419 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2420 | Encoded-Unicast-RP-Address-2 | 2421 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2422 | RP2-Holdtime | RP2-Priority | Reserved | 2423 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2424 | . | 2425 | . | 2426 | . | 2427 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2428 | Encoded-Unicast-RP-Address-m | 2429 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2430 | RPm-Holdtime | RPm-Priority | Reserved | 2431 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2433 PIM Version, Type, Reserved, Checksum 2434 Described above. 2436 Fragment Tag 2437 A randomly generated number, acts to distinguish the 2438 fragments belonging to different Bootstrap messages; 2439 fragments belonging to same Bootstrap message carry the 2440 same `Fragment Tag'. 2442 Hash Mask len 2443 The length (in bits) of the mask to use in the hash 2444 function. For IPv4 we recommend a value of 30. For IPv6 we 2445 recommend a value of 126. 2447 BSR-priority 2448 Contains the BSR priority value of the included BSR. This 2449 field is considered as a high order byte when comparing BSR 2450 addresses. 2452 Encoded-Unicast-BSR-Address 2453 The address of the bootstrap router for the domain. The 2454 format for this address is given in the Encoded-Unicast- 2455 Address in 4.1. .IP "Encoded-Group Address-1..n" 2456 The group prefix (address and mask) with which the 2457 Candidate RPs are associated. Format previously described. 2459 RP-Count-1..n 2460 The number of Candidate RP addresses included in the whole 2461 Bootstrap message for the corresponding group prefix. A 2462 router does not replace its old RP-Set for a given group 2463 prefix until/unless it receives `RP-Count' addresses for 2464 that prefix; the addresses could be carried over several 2465 fragments. If only part of the RP-Set for a given group 2466 prefix was received, the router discards it, without 2467 updating that specific group prefix's RP-Set. 2469 Frag RP-Cnt-1..m 2470 The number of Candidate RP addresses included in this 2471 fragment of the Bootstrap message, for the corresponding 2472 group prefix. The `Frag RP-Cnt' field facilitates parsing 2473 of the RP-Set for a given group prefix, when carried over 2474 more than one fragment. 2476 Encoded-Unicast-RP-address-1..m 2477 The address of the Candidate RPs, for the corresponding 2478 group prefix. The format for this address is given in the 2479 Encoded-Unicast-Address in 4.1. .IP "RP1..m-Holdtime" 2480 The Holdtime for the corresponding RP. This field is 2481 copied from the `Holdtime' field of the associated RP 2482 stored at the BSR. 2484 RP1..m-Priority 2485 The `Priority' of the corresponding RP and Encoded-Group 2486 Address. This field is copied from the `Priority' field 2487 stored at the BSR when receiving a Candidate-RP- 2488 Advertisement. The highest priority is `0' (i.e. the lower 2489 the value of the `Priority' field, the higher). Note that 2490 the priority is per RP per Encoded-Group Address. 2492 4.7 Assert Message 2494 The Assert message is sent when a multicast data packet is 2495 received on an outgoing interface corresponding to the (S,G) or 2496 (*,G) associated with the source. 2498 0 1 2 3 2499 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 2500 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2501 |PIM Ver| Type | Reserved | Checksum | 2502 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2503 | Encoded-Group Address | 2504 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2505 | Encoded-Unicast-Source Address | 2506 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2507 |R| Metric Preference | 2508 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2509 | Metric | 2510 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2512 PIM Version, Type, Reserved, Checksum 2513 Described above. 2515 Encoded-Group Address 2516 The group address to which the data packet was addressed, 2517 and which triggered the Assert. Format previously 2518 described. 2520 Encoded-Unicast-Source Address 2521 Source address from multicast datagram that triggered the 2522 Assert packet to be sent. The format for this address is 2523 given in the Encoded-Unicast-Address in 4.1. .IP "R" 2524 RPT-bit is a 1 bit value. If the multicast datagram that 2525 triggered the Assert packet is routed down the RP tree, 2526 then the RPT-bit is 1; if the multicast datagram is routed 2527 down the SPT, it is 0. 2529 Metric Preference 2530 Preference value assigned to the unicast routing protocol 2531 that provided the route to Host address. 2533 Metric The unicast routing table metric. The metric is in units 2534 applicable to the unicast routing protocol used. 2536 4.8 Graft Message 2538 Used in dense-mode. Refer to PIM dense mode specification. 2540 4.9 Graft-Ack Message 2542 Used in dense-mode. Refer to PIM dense mode specification. 2544 4.10 Candidate-RP-Advertisement 2546 Candidate-RP-Advertisements are periodically unicast from the 2547 C-RPs to the BSR. 2549 0 1 2 3 2550 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 2551 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2552 |PIM Ver| Type | Reserved | Checksum | 2553 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2554 | Prefix-Cnt | Priority | Holdtime | 2555 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2556 | Encoded-Unicast-RP-Address | 2557 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2558 | Encoded-Group Address-1 | 2559 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2560 | . | 2561 | . | 2562 | . | 2563 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2564 | Encoded-Group Address-n | 2565 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2567 PIM Version, Type, Reserved, Checksum 2568 Described above. 2570 Prefix-Cnt 2571 The number of encoded group addresses included in the 2572 message; indicating the group prefixes for which the C-RP 2573 is advertising. A Prefix-Cnt of `0' implies a prefix of 2574 224.0.0.0 with mask length of 4; i.e. all multicast groups. 2575 If the C-RP is not configured with Group-prefix 2576 information, the C-RP puts a default value of `0' in this 2577 field. 2579 Priority 2580 The `Priority' of the included RP, for the corresponding 2581 Encoded-Group Address (if any). highest priority is `0' 2582 (i.e. the lower the value of the `Priority' field, the 2583 higher the priority). This field is stored at the BSR upon 2584 receipt along with the RP address and corresponding 2585 Encoded-Group Address. 2587 Holdtime 2588 The amount of time the advertisement is valid. This field 2589 allows advertisements to be aged out. 2591 Encoded-Unicast-RP-Address 2592 The address of the interface to advertise as a Candidate 2593 RP. The format for this address is given in the Encoded- 2594 Unicast-Address in 4.1. .IP "Encoded-Group Address-1..n" 2595 The group prefixes for which the C-RP is advertising. 2596 Format previously described. 2598 5 Acknowledgments 2600 Tony Ballardie, Scott Brim, Jon Crowcroft, Bill Fenner, Paul 2601 Francis, Joel Halpern, Horst Hodel, Polly Huang, Stephen 2602 Ostrowski, Lixia Zhang and Girish Chandranmenon provided 2603 detailed comments on previous drafts. The authors of CBT [8] and 2604 membership of the IDMR WG provided many of the motivating ideas 2605 for this work and useful feedback on design details. 2607 This work was supported by the National Science Foundation, 2608 ARPA, cisco Systems and Sun Microsystems. 2610 6 Appendices 2611 6.1 Appendix I: Major Changes and Updates to the Spec 2613 This appendix populates the major changes in the specification 2614 document as compared to `draft-ietf-idmr-pim-spec-01.ps,txt'. 2616 bsubsection*Major Changes 2618 List of changes since March '96 IETF: 2620 1. (*,*,RP) Joins state and data forwarding check; replaces (*,G- 2621 Prefix) Joins state for interoperability. (*,G) negative cache 2622 introduced for the (*,*,RP) state supporting mechanisms. 2624 2. Semantic fragmentation for the Bootstrap message. 2626 3. Refinement of Assert details. 2628 4. Addition and refinement of Join/Prune suppression and Register 2629 suppression (introduction of null Registers). 2631 5. Editorial changes and clarifications to the timers section. 2633 6. Addition of Appendix II (BSR Election and RP-Set Distribution), 2634 and Appendix III (Glossary of Terms). 2636 7. Addition of table of contents. 2638 List of changes incurred since version 1 of the spec.: 2640 1. Proposal and refinement of bootstrap router (BSR) election 2641 mechanisms 2643 2. Introduction of hash functions for Group to RP mapping 2645 3. New RP-liveness indication mechanisms based upon the the 2646 Bootstrap Router (BSR) and the Bootstrap messages. 2648 4. Removal of reachability messages, RP reports and multiple RPs 2649 per group. 2651 *Packet Format Changes 2653 Packet Format incurred updates to accommodate different address 2654 lengths, and address aggregation. 2656 1 The `Addr Family' and `Encoding Type' fields were added to 2657 the packet formats. 2659 2 The Encoded source and group address formats were 2660 introduced, with the use of a `Mask length' field to allow 2661 aggregation, section 4.1. 2663 3 Packet formats are no longer IGMP messages; rather PIM 2664 messages. 2666 PIM message types and formats were also modified: 2668 [Note: most changes were made to the May 95 version, unless 2669 otherwise specified]. 2671 1 Obsolete messages: 2673 Register-Ack [Feb. 96] 2675 Poll and Poll Response [Feb. 96] 2677 RP-Reachability [Feb. 96] 2679 RPlist-Mapping [Feb. 96] 2681 2 New messages: 2683 Candidate-RP-Advertisement [change made in October 95] 2684 RP-Set [Feb. 96] 2686 3 Modified messages: 2688 Join/Prune [Feb. 96] 2689 Register [Feb. 96] 2690 Register-Stop [Feb. 96] 2691 Hello (addition of OptionTypes) [Aug 96] 2693 4 Renamed messages: 2695 Query messages are renamed as Hello messages [Aug. 96] 2696 RP-Set messages are renamed as Bootstrap messages [Aug. 96] 2697 6.2 Appendix II: BSR Election and RP-Set Distribution 2699 For simplicity, the bootstrap message is used in both the BSR 2700 election and the RP-Set distribution mechanisms. These 2701 mechanisms are described by the following state machine, 2702 illustrated in figure 4. The protocol transitions for a 2703 Candidate-BSR are given in state diagram (a). For routers not 2704 configured as Candidate-BSRs, the protocol transitions are given 2705 in state diagram (b). 2707 [Figures are present only in the postscript version] 2708 Fig. 4 State Diagram for the BSR election and RP-Set distribution 2710 Each PIM router keeps a bootstrap-timer, initialized to 2711 [Bootstrap-Timeout], in addition to a local BSR field 2712 `LclBSR' (initialized to a local address if Candidate-BSR, or 2713 to 0 otherwise), and a local RP-Set `LclRP-Set' (initially 2714 empty). The main stimuli to the state machine are timer events 2715 and arrival of bootstrap messages: 2717 bsubsection*Initial States and Timer Events 2719 1 2721 2 If the router is a Candidate-BSR: 2723 1 2725 2 The router operates initially in the `CandBSR' state, 2726 where it does not originate any bootstrap messages. 2728 3 If the bootstrap-timer expires, and the current state 2729 is `CandBSR', the router originates a bootstrap 2730 message carrying the local RP-Set and its own BSR 2731 priority and address, restarts the bootstrap-timer at 2732 [Bootstrap-Period] seconds, and transits into the 2733 `ElectedBSR' state. Note that the actual sending of 2734 the bootstrap message may be delayed by a random value 2735 to reduce transient control overhead. To obtain best 2736 results, the random value is set such that the 2737 preferred BSR is the first to originate a bootstrap 2738 message. We propose the following as an efficient 2739 implementation of the random value delay (in seconds): 2741 Delay = 5 + 2 * log_2(1 + bestPriority - myPriority) + AddrDelay 2743 where myPriority is the Candidate-BSR's 2744 configured priority, and bestPriority equals: 2746 bestPriority = Max(storedPriority, myPriority) ] 2748 and AddrDelay is given by the following: 2750 1 if ( bestPriority equals myPriority) then 2751 [AddrDelay = log_2(bestAddr - myAddr) / 16, ] 2753 2 else [AddrDelay = 2 - (myAddr / 2^31) ] 2755 where myAddr is the Candidate-BSR's address, and 2756 bestAddr is the stored BSR's address. 2758 4 If the bootstrap-timer expires, and the current state 2759 is `ElectedBSR', the router originates a bootstrap 2760 message, and restarts the RP-Set timer at [Bootstrap- 2761 Period]. No state transition is incurred. 2763 This way, the elected BSR originates periodic 2764 bootstrap messages every [Bootstrap-Period]. 2766 3 If a router is not a Candidate-BSR: 2768 1 2770 2 The router operates initially in the `AxptAny' state. 2771 In such state, a router accepts the first bootstrap 2772 message from the The Reverse Path Forwarding (RPF) 2773 neighbor toward the included BSR. The RPF neighbor in 2774 this case is the next hop router en route to the 2775 included BSR. 2777 3 If the bootstrap-timer expires, and the current state 2778 is `AxptPref'-- where the router accepts only 2779 preferred bootstrap messages (those that carry BSR- 2780 priority and address higher than, or equal to, 2781 `LclBSR') from the RPF neighbor toward the included 2782 BSR-- the router transits into the `AxptAny' state. 2784 In this case, if an elected BSR becomes unreachable, 2785 the routers start accepting bootstrap messages from 2786 another Candidate-BSR after the bootstrap-timer 2787 expires. All PIM routers within a domain converge on 2788 the preferred reachable Candidate-BSR. 2790 Receiving Bootstrap Message: 2792 To avoid loops, an RPF check is performed on the included BSR 2793 address. Upon receiving a bootstrap message from the RPF 2794 neighbor toward the included BSR, the following actions are 2795 taken: 2797 1 If the router is not a Candidate-BSR: 2799 1 If the current state is `AxptAny', the router accepts 2800 the bootstrap message, and transits into the 2801 `AxptPref' state. 2803 2 If the current state is `AxptPref', and the bootstrap 2804 message is preferred, the message is accepted. No 2805 state transition is incurred. 2807 2 If the router is a Candidate-BSR, and the bootstrap message 2808 is preferred, the message is accepted. Further, if this 2809 happens when the current state is `Elected BSR', the router 2810 transits into the `CandBSR' state. 2812 When a bootstrap message is accepted, the router restarts the 2813 bootstrap-timer at [Bootstrap-Timeout], stores the received BSR 2814 priority and address in `LclBSR', and the received RP-Set in 2815 `LclRP-Set', and forwards the bootstrap message out all 2816 interfaces except the receiving interface. 2818 If a bootstrap message is rejected, no state transitions are 2819 triggered. 2821 6.3 Appendix III: Glossary of Terms 2823 Following is an alphabetized list of terms and definitions used 2824 throughout this specification. 2826 * { Bootstrap router (BSR)}. A BSR is a dynamically elected 2827 router within a PIM domain. It is responsible for 2828 constructing the RP-Set and originating Bootstrap messages. 2830 * { Candidate-BSR (C-BSR)}. A C-BSR is a router configured to 2831 participate in the BSR election and act as BSRs if elected. 2833 * { Candidate RP (C-RP)}. A C-RP is a router configured to 2834 send periodic Candidate-RP-Advertisement messages to the 2835 BSR, and act as an RP when it receives Join/Prune or 2836 Register messages for the advertised group prefix. 2838 * { Designated Router (DR)}. The DR sets up multicast route 2839 entries and sends corresponding Join/Prune and Register 2840 messages on behalf of directly-connected receivers and 2841 sources, respectively. The DR may or may not be the same 2842 router as the IGMP Querier. The DR may or may not be the 2843 long-term, last-hop router for the group; a router on the 2844 LAN that has a lower metric route to the data source, or to 2845 the group's RP, may take over the role of sending 2846 Join/Prune messages. 2848 * { Incoming interface (iif)}. The iif of a multicast route 2849 entry indicates the interface from which multicast data 2850 packets are accepted for forwarding. The iif is initialized 2851 when the entry is created. 2853 * Join list. The Join list is one of two lists of addresses 2854 that is included in a Join/Prune message; each address 2855 refers to a source or RP. It indicates those sources or RPs 2856 to which downstream receiver(s) wish to join. 2858 * { Last-hop router}. The last-hop router is the last router 2859 to receive multicast data packets before they are delivered 2860 to directly-connected member hosts. In general the last-hop 2861 router is the DR for the LAN. However, under various 2862 conditions described in this document a parallel router 2863 connected to the same LAN may take over as the last-hop 2864 router in place of the DR. 2866 * { Outgoing interface (oif) list}. Each multicast route 2867 entry has an oif list containing the outgoing interfaces to 2868 which multicast packets should be forwarded. 2870 * Prune List. The Prune list is the second list of addresses 2871 that is included in a Join/Prune message. It indicates 2872 those sources or RPs from which downstream receiver(s) wish 2873 to prune. 2875 * { PIM Multicast Border Router (PMBR)}. A PMBR connects a 2876 PIM domain to other multicast routing domain(s). 2878 * { Rendezvous Point (RP)}. Each multicast group has a 2879 shared-tree via which receivers hear of new sources and new 2880 receivers hear of all sources. The RP is the root of this 2881 per-group shared tree, called the RP-Tree. 2883 * { RP-Set}. The RP-Set is a set of RP addresses constructed 2884 by the BSR based on Candidate-RP advertisements received. 2885 The RP-Set information is distributed to all PIM routers in 2886 the BSR's PIM domain. 2888 * { Reverse Path Forwarding (RPF)}. RPF is used to select the 2889 appropriate incoming interface for a multicast route entry 2890 . The RPF neighbor for an address X is the the next-hop 2891 router used to forward packets toward X. The RPF interface 2892 is the interface to that RPF neighbor. In the common case 2893 this is the next hop used by the unicast routing protocol 2894 for sending unicast packets toward X. For example, in cases 2895 where unicast and multicast routes are not congruent, it 2896 can be different. 2898 * { Route entry.} A multicast route entry is state maintained 2899 in a router along the distribution tree and is created, and 2900 updated based on incoming control messages. The route entry 2901 may be different from the forwarding entry; the latter is 2902 used to forward data packets in real time. Typically a 2903 forwarding entry is not created until data packets arrive, 2904 the forwarding entry's iif and oif list are copied from the 2905 route entry, and the forwarding entry may be flushed and 2906 recreated at will. 2908 * { Shortest path tree (SPT)}. The SPT is the multicast 2909 distribution tree created by the merger of all of the 2910 shortest paths that connect receivers to the source (as 2911 determined by unicast routing). 2913 * { Sparse Mode (SM)}. SM is one mode of operation of a 2914 multicast protocol. PIM SM uses explicit Join/Prune 2915 messages and Rendezvous points in place of Dense Mode PIM's 2916 and DVMRP's broadcast and prune mechanism. 2918 * { Wildcard (WC) multicast route entry}. Wildcard multicast 2919 route entries are those entries that may be used to forward 2920 packets for any source sending to the specified group. 2921 Wildcard bots in the join list of a Join/Prune message 2922 represent either a (*,G) or (*,*,RP) join; in the prune 2923 list they represent a (*,G) prune. 2925 * { (S,G) route entry}. (S,G) is a source-specific route 2926 entry. It may be created in response to data packets, 2927 Join/Prune messages, or Asserts. The (S,G) state in routers 2928 creates a source-rooted, shortest path (or reverse shortest 2929 path) distribution tree. (S,G)RPT bit entries are source- 2930 specific entries on the shared RP-Tree; these entries are 2931 used to prune particular sources off of the shared tree. 2933 * { (*,G) route entry}. Group members join the shared RP-Tree 2934 for a particular group. This tree is represented by (*,G) 2935 multicast route entries along the shortest path branches 2936 between the RP and the group members. 2938 * { (*,*,RP) route entry}. (*,*,RP) refers to any source and 2939 any multicast group that maps to the RP included in the 2940 entry. The routers along the shortest path branches between 2941 a domain's RP(s) and its PMBRs keep (*,*,RP) state and use 2942 it to determine how to deliver packets toward the PMBRs if 2943 data packets arrive for which there is not a longer match. 2944 The wildcard group in the (*,*,RP) route entry is 2945 represented by a group address of 224.0.0.0 and a mask 2946 length of 4 bits. 2948 References 2950 1. S.Deering, D.Estrin, D.Farinacci, V.Jacobson, C.Liu, L.Wei, 2951 P.Sharma, and A.Helmy. Protocol independent multicast (pim) : 2952 Motivation and architecture. 2953 Internet Draft, May 1995. 2955 2. S.Deering, D.Estrin, D.Farinacci, V.Jacobson, C.Liu, and L.Wei. 2956 The pim architecture for wide-area multicast routing. 2957 ACM Transactions on Networks, April 1996. 2959 3. D.Estrin, D.Farinacci, V.Jacobson, C.Liu, L.Wei, P.Sharma, and 2960 A.Helmy. Protocol independent multicast-dense mode (pim-dm) : 2961 Protocol specification. Internet Draft, November 1995. 2963 4. S.Deering. Host extensions for ip multicasting, aug 1989. 2964 RFC1112. 2966 5. W.Fenner. Internet group management protocol, version 2. 2967 Internet Draft, May 1996. 2969 6. R.Atkinson. Security architecture for the internet protocol, 2970 August 1995. RFC-1825. 2972 7. MarkR. Nelson. File verification using CRC. Dr. Dobb's 2973 Journal, May 1992. 2975 8. A.J. Ballardie, P.F. Francis, and J.Crowcroft. Core based trees. 2976 In Proceedings of the ACM SIGCOMM, San Francisco, 1993. 2978 Addresses of Authors: 2980 Deborah Estrin 2981 Computer Science Dept/ISI 2982 University of Southern Calif. 2983 Los Angeles, CA 90089 2984 estrin@usc.edu 2986 Dino Farinacci 2987 Cisco Systems Inc. 2988 170 West Tasman Drive, 2989 San Jose, CA 95134 2990 dino@cisco.com 2992 Ahmed Helmy 2993 Computer Science Dept. 2994 University of Southern Calif. 2995 Los Angeles, CA 90089 2996 ahelmy@catarina.usc.edu 2998 David Thaler 2999 EECS Department 3000 University of Michigan 3001 Ann Arbor, MI 48109 3002 thalerd@eecs.umich.edu 3004 Stephen Deering 3005 Xerox PARC 3006 3333 Coyote Hill Road 3007 Palo Alto, CA 94304 3008 deering@parc.xerox.com 3010 Mark Handley 3011 Department of Computer Science 3012 University College London 3013 Gower Street 3014 London, WC1E 6BT 3015 UK 3016 m.handley@cs.ucl.ac.uk 3018 Van Jacobson 3019 Lawrence Berkeley Laboratory 3020 1 Cyclotron Road 3021 Berkeley, CA 94720 3022 van@ee.lbl.gov 3024 Ching-gung Liu 3025 Computer Science Dept. 3026 University of Southern Calif. 3027 Los Angeles, CA 90089 3028 charley@catarina.usc.edu 3030 Puneet Sharma 3031 Computer Science Dept. 3032 University of Southern Calif. 3033 Los Angeles, CA 90089 3034 puneet@catarina.usc.edu 3036 Liming Wei 3037 Cisco Systems Inc. 3038 170 West Tasman Drive, 3039 San Jose, CA 95134 3040 lwei@cisco.com