idnits 2.17.1 draft-ietf-idmr-pim-sm-spec-04.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 (2024-03-28) 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) 2024 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 63 longer pages, the longest (page 21) being 61 lines == It seems as if not all pages are separated by form feeds - found 0 form feeds but 67 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 846 instances of weird spacing in the document. Is it really formatted ragged-right, rather than justified? ** There are 39 instances of too long lines in the document, the longest one being 18 characters in excess of 72. == There are 9 instances of lines with non-RFC6890-compliant IPv4 addresses in the document. If these are example addresses, they should be changed. == There are 4 instances of lines with multicast IPv4 addresses in the document. If these are generic example addresses, they should be changed to use the 233.252.0.x range defined in RFC 5771 Miscellaneous warnings: ---------------------------------------------------------------------------- == Line 19 has weird spacing: '... Drafts are ...' == Line 20 has weird spacing: '...cuments of t...' == Line 21 has weird spacing: '...ups may also ...' == Line 25 has weird spacing: '... Drafts may ...' == Line 26 has weird spacing: '...iate to use ...' == (841 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 43 looks like a reference -- Missing reference section? '2' on line 43 looks like a reference -- Missing reference section? '3' on line 59 looks like a reference -- Missing reference section? '4' on line 117 looks like a reference -- Missing reference section? '5' on line 1747 looks like a reference -- Missing reference section? '6' on line 2365 looks like a reference Summary: 14 errors (**), 0 flaws (~~), 12 warnings (==), 7 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group Steven Deering (XEROX) 3 Internet Draft Deborah Estrin (USC) 4 Dino Farinacci (CISCO) 5 Mark Handley (UCL) 6 Ahmed Helmy (USC) 7 Van Jacobson (LBL) 8 Chinggung Liu (USC) 9 Puneet Sharma (USC) 10 David Thaler (UMICH) 11 Liming Wei (CISCO) 12 Expire in six months 14 Protocol Independent Multicast-Sparse Mode (PIM-SM): Protocol 15 Specification 17 Status of This Memo 19 This document is an Internet Draft. Internet Drafts are working 20 documents of the Internet Engineering Task Force (IETF), its Areas, 21 and its Working Groups. (Note that other groups may also distribute 22 working documents as Internet Drafts). 24 Internet Drafts are draft documents valid for a maximum of six 25 months. Internet Drafts may be updated, replaced, or obsoleted by 26 other documents at any time. It is not appropriate to use Internet 27 Drafts as reference material or to cite them other than as a 28 ``working'' draft'' or ``work in progress.'' 30 Please check the I-D abstract listing contained in each Internet 31 Draft directory to learn the current status of this or any other 32 Internet Draft. 34 1 Introduction 36 This document describes a protocol for efficiently routing to 37 multicast groups that may span wide-area (and inter-domain) 38 internets. We refer to the approach as Protocol Independent 39 Multicast--Sparse Mode (PIM-SM) because it is not dependent on any 40 particular unicast routing protocol, and because it is designed to 41 support sparse groups as defined in [1][2]. This document describes 42 the protocol details. For the motivation behind the design and a 43 description of the architecture, see [1][2]. Section 2 summarizes 44 PIM-SM operation. It describes the protocol from a network 45 perspective, in particular, how the participating routers interact to 46 create and maintain the multicast distribution tree. Section 3 47 describes PIM-SM operations from the perspective of a single router 48 implementing the protocol; this section constitutes the main body of 49 the protocol specification. It is organized according to PIM-SM 50 message type; for each message type we describe its contents, its 51 generation, and its processing. 53 Section 4 provides packet format details. Sections 3.8 and 3.9 54 summarize the timers and flags referred to throughout this document. 56 The most significant functional changes since the January '95 version 57 involve the Rendezvous Point-related mechanisms, several resulting 58 simplifications to the protocol, and removal of the PIM-DM protocol 59 details to a separate [3] (for clarity). 61 2 PIM-SM Protocol Overview 63 In this section we provide an overview of the architectural 64 components of PIM-SM. 66 A router [*] 68 receives explicit Join/Prune messages from those neighboring routers 69 that have downstream group members. The router then forwards data 70 packets addressed to a multicast group, G, only onto those interfaces 71 on which explicit joins have been received. 73 A Designated Router (DR) sends periodic Join/Prune messages toward a 74 group-specific Rendezvous Point (RP) for each group for which it has 75 active members. Each router along the path toward the RP builds a 76 wildcard (any-source) forwarding state. for the group and sends 77 _________________________ 78 [*] All routers mentioned in this document are assumed 79 to be PIM-SM capable, unless otherwise specified. 81 messages on toward the RP. We use the term entry to refer to the 82 forwarding state maintained in a router to represent the distribution 83 tree. Each entry includes such things as the incoming interface from 84 which packets are accepted, the list of outgoing interfaces to which 85 packets are sent, timers, flag bits, etc. The wildcard forwarding 86 entry's incoming interface points toward the RP; the outgoing 87 interfaces point to the neighboring downstream routers that have sent 88 Join/Prune messages toward the RP. This forwarding state creates a 89 shared, RP-centered, distribution tree that reaches all group 90 members. When a data source first sends to a group, its DR unicasts 91 Register messages to the RP with the source's data packets 92 encapsulated within. If the data rate is high, the RP can send 93 source-specific Join/Prune messages back towards the source and the 94 source's data packets will follow the resulting forwarding state and 95 travel unencapsulated to the RP. Whether they arrive encapsulated or 96 natively, the RP forwards the source's decapsulated data packets down 97 the RP-centered distribution tree toward group members. If the data 98 rate warrants it, routers with local receivers can join a source- 99 specific, shortest path, distribution tree, and prune these source's 100 packets off of the shared RP-centered tree. Even if all receivers 101 switch to the shortest path tree, state for that source will be kept 102 at the RP, so that new members that join the RP-centered tree will 103 receive data packets from the source. For low data rate sources, 104 neither the RP, nor last-hop routers need join a source-specific 105 shortest path tree and data packets can be delivered via the shared, 106 RP-tree. 108 The following subsections describe SM operation in more detail, in 109 particular, the control messages, and the actions they trigger. 110 Section 3 describes protocol operation from an implementors 111 perspective, i.e., the actions performed by a single router. 113 2.1 Local hosts joining a group 115 In order to join a multicast group, G, a host sends an IGMP Host- 116 Membership-Report message identifying the particular group. As 117 specified in [4], IGMP Host-Membership-Report messages are sent in 118 response to a directly-connected router's IGMP Host-Membership-Query 119 message (see figure 1) [*] From this point on we refer to such a 120 host as a receiver, R, (or member) of the group G. 122 _________________________ 123 [*] All figures used in this section are for illustra- 124 tion and are not intended to be complete. For complete 125 and detailed protocol action see Section 3 . 127 Fig. 1 Example: how a receiver joins, and sets up shared tree 129 When a DR receives an IGMP Host-Membership-Report for a new group, G, 130 the DR looks up the associated RP. The DR (e.g., router A in figure 131 1) creates a wildcard multicast forwarding entry for the group, 132 referred to here as a (*,G) entry; if there is no more specific match 133 for a particular source, the packet will be forwarded according to 134 this entry. 136 The RP address is included in a special field in the forwarding entry 137 and is included in periodic upstream Join/Prune messages. The 138 outgoing interface is set to that over which the IGMP Host- 139 Membership-Report was received from the new member. The incoming 140 interface is set to the interface used to send unicast packets to the 141 RP. The RPT-bit flag associated with this entry is also set to 1, 142 indicating that this entry, (*,G), represents state on the shared 143 RP-tree. Each DR on the RP-tree with directly connected members sets 144 a timer for this entry. If the timer expires and the DR has neither 145 local members nor downstream receivers, the (*,G) state is deleted. 146 If the DR does have local members, it refreshes the (*,G) entry timer 147 each time it gets an IGMP Host-Membership-Report. 149 2.2 Establishing the RP-rooted shared tree 151 Triggered by the (*,G) state, the DR creates a Join/Prune message 152 with the RP address in its join list and the the WC-bit and RPT-bit 153 set to 1. The prune list is left empty. When the RPT-bit is set to 1 154 it indicates that the join is associated with the shared RP-tree and 155 therefore the Join/Prune message is propagated along the RP-tree. 156 When the WC-bit is set to 1 it indicates that the address is an RP 157 and the downstream receivers expect to receive packets from all 158 sources via this (shared tree) path; WC stands for wildcard 159 [*] 161 Each upstream router creates or updates its multicast forwarding 162 _________________________ 163 [*] Note that the term RPT-bit is used to refer to both 164 the RPT-bit flags associated with forwarding entries, 165 and the RPT-bit included in each encoded address in a 166 Join/Prune message. 168 entry for (*,G) when it receives a Join/Prune with the RPT-bit and 169 WC-bit set. The interface on which the Join/Prune message arrived is 170 added to the list of outgoing interfaces (oifs) for (*,G). Based on 171 this entry each upstream router between the receiver and the RP sends 172 a Join/Prune message in which the join list includes the RP. The 173 packet payload contains Multicast-Address=G, Join=RP,WC-bit,RPT-bit, 174 Prune=NULL. 176 2.3 Hosts sending to a group 178 When a host starts sending multicast data packets to a group, 179 initially its DR must deliver each packet to the RP for distribution 180 down the RP-tree (see figure 2). The sender's DR initially 181 encapsulates each data packet in a Register message and unicasts it 182 to the RP for that group. The RP decapsulates each Register message 183 and forwards the enclosed data packet natively to downstream members 184 on the shared RP-tree. 186 Fig. 2 Example: a host sending to a group 188 If the data rate of the source warrants [*] 190 the use of a source-specific shortest path tree (SPT), the RP may 191 construct a new multicast forwarding entry that is specific to the 192 source, hereafter referred to as (S,G) state, and send periodic 193 Join/Prune messages toward the source. The routers between the source 194 and the RP build and maintain (S,G) state in response to these 195 messages and send (S,G) messages upstream toward the source. 197 The source's DR must stop encapsulating data packets in Registers 198 when (and so long as) it receives Register-Stop messages from the RP. 199 The RP triggers Register-Stop messages in response to Registers, if 200 the RP has no downstream receivers for the group (or for that 201 particular source), or if the RP has already joined the (S,G) tree 202 _________________________ 203 [*] This decision is a local policy established at the 204 RP. For example, when the Register rate exceeds a con- 205 figured threshold at the RP, this may warrant the use 206 of the SPT. 208 and is receiving the data packets natively. Each source's DR 209 maintains, per (S,G), a Register-bit and a Register-bit timer. The 210 Register-bit timer is started by the Register-Stop message; upon 211 expiration, the Register-bit is set to 1 and the source's DR resumes 212 sending data packets encapsulated in Register messages. 214 2.4 Switching from shared tree (RP-tree) to shortest path tree (SP- 215 tree) 217 When a router has directly-connected members, it first joins the 218 shared RP-tree. The router can switch to a source's shortest path 219 tree (SP-tree) after receiving packets from that source over the 220 shared RP-tree. The recommended policy is to initiate the switch to 221 the SP-tree after receiving a significant number of data packets 222 during a specified time interval from a particular source. To realize 223 this policy the router can monitor data packets from sources for 224 which it has no source-specific multicast forwarding entry and 225 initiate such an entry when the data rate exceeds the configured 226 threshold. As shown in figure 3, router `A' initiates a (S,G) state. 228 Fig. 3 Example: Switching from shared tree to shortest path tree 230 When a (S,G) entry is activated (and periodically so long as the 231 state exists), a Join/Prune message is sent upstream towards the 232 source, S, with S in the join list. The payload contains Multicast- 233 Address=G, Join=S, Prune=NULL. When the (S,G) entry is created, the 234 outgoing interface list is copied from (*,G), i.e., all local shared 235 tree branches are replicated in the new shortest path tree [*] In 236 this way when a data packet from S arrives and matches on this entry, 237 all receivers will continue to receive the source's packets along 238 this path. Note that (S,G) state must be maintained in each last-hop 239 router that is responsible for initiating and maintaining an SP-tree. 240 [*] 241 _________________________ 242 [*] In more complicated scenarios, other entries in the 243 router have to be considered. For details see Section 3. 244 [*] By last-hop router we mean the router that delivers 245 the packets to their ultimate end-system destination. 246 This is the router that monitors if there is group 247 membership and joins or prunes the appropriate distri- 248 Even when (*,G) and (S,G) overlap, both states are needed to trigger 249 the source-specific Join/Prune messages. (S,G) state is kept alive by 250 data packets arriving from that source. A timer, S-timer, is set for 251 the (S,G) entry and this timer is restarted whenever a data packet 252 for (S,G) is forwarded out at least one oif. When the S-timer expires 253 the state is deleted. 255 Only the RP and routers with local members can initiate switching to 256 the SP-tree; intermediate routers do not. Consequently, last-hop 257 routers create (S,G) state in response to data packets from the 258 source, S; whereas intermediate routers only create (S,G) state in 259 response to Join/Prune messages from downstream that have S in the 260 Join list [*] 262 The (S,G) entry is initialized with the SPT-bit cleared, indicating 263 that the shortest path tree branch from S has not yet been setup 264 completely, and the router can still accept packets from S that 265 arrive on the (*,G) entry's indicated incoming interface (iif). [*] 267 When a router with a (S,G) entry and a cleared SPT-bit starts to 268 receive packets from the new source S on the iif for the (S,G) entry, 269 and that iif differs from the (*,G) entry's iif, the router sets the 270 SPT-bit, and sends a Join/Prune message towards the RP, indicating 271 that the router no longer wants to receive packets from S via the 272 shared RP-tree. The Join/Prune message sent towards the RP includes S 273 in the prune list, with the RPT-bit set indicating that S's packets 274 should not be forwarded down this branch of the shared tree. If the 275 router receiving the Join/Prune message has (S,G) state (with or 276 without the forwarding entry's RPT-bit flag set), it deletes the 277 arriving interface from the (S,G) oif list. If the router has only 278 (*,G) state, it creates an entry with the RPT-bit flag set to 1. For 279 brevity we refer to an (S,G) entry that has the RPT-bit flag set to 1 280 _________________________ 281 bution trees in response. In general the last-hop 282 router is the Desgnated Router (DR) for the LAN. Howev- 283 er, under various conditions described later, a paral- 284 lel router connected to the same LAN may take over as 285 the last-hop router in place of the DR. 286 [*] For example, to implement the policy that source- 287 specific trees are only setup for high-data rate 288 source, a last-hop router might not create a (S,G) en- 289 try until it has received m data packets from the 290 source within some interval of n seconds. 291 [*] As in DVMRP, each PIM multicast forwarding entry 292 has an associated incoming interface on which packets 293 are expected to arrive. 295 as an (S,G)RPT-bit entry. This notational distinction is useful to 296 point out the different actions taken for (S,G) entries depending on 297 the setting of the RPT-bit flag. Note that a router can have no more 298 than one (S,G) entry for any particular S and G, at any particular 299 time; whether the RPT-bit flag is set or not. In other words, a 300 router never has both an (S,G) and an (S,G)RPT-bit entry for the same 301 S and G at the same time. The Join/Prune message payload contains 302 Multicast-Address=G, Join=NULL, Prune=S,RPT-bit. 304 A new receiver may join an existing RP-tree on which source-specific 305 prune state has been established (e.g., because downstream receivers 306 have switched to SP-trees). In this case the prune state must be 307 eradicated upstream of the new receiver to bring all sources' data 308 packets down to the new receiver. Therefore, when a (*,G) Join 309 arrives at a router that has any (Si,G)RPT-bit entries (i.e., entries 310 that cause the router to send source-specific prunes toward the RP), 311 these entries must be updated upstream of the router so as to bring 312 all sources' packets down to the new member. To accomplish this, each 313 router that receives a (*,G) Join/Prune message updates any existing 314 (S,G)RPT-bit entries. The router may also trigger a (*,G) join 315 upstream to cause the same updating of RPT-bit settings upstream and 316 pull down all active sources' packets. If the arriving (*,G) join has 317 some sources included in its prune list, then the corresponding 318 (S,G)RPT-bit entries are left unchanged (i.e., the RPT-bit remains 319 set and no oif is added). 321 2.5 Steady state maintenance of distribution tree (i.e., router state) 323 In the steady state each router sends periodic Join/Prune messages 324 for each active PIM forwarding entry; the Join/Prune messages are 325 sent to the neighbor indicated in the iif field of the corresponding 326 entry. These messages are sent periodically to capture state, 327 topology, and membership changes. A Join/Prune message is also sent 328 on an event-triggered basis each time a new forwarding entry is 329 established for some new source (note that some damping function may 330 be applied, e.g., a merge time). Join/Prune messages do not elicit 331 any form of explicit acknowledgment; routers recover from lost 332 packets using the periodic refresh mechanism. 334 2.6 Obtaining RP information 336 To obtain the RP information, all routers within a PIM domain collect 337 RP-Set messages. RP-Set messages are sent hop-by-hop within the 338 domain; the domain's bootstrap router (BSR) is responsible for 339 originating the RP-set messages. The BSR is elected dynamically 340 within each domain. 342 [*] 344 Routers then use the set of RPs to get the proper Group to RP 345 mapping. Details are as follows: 347 A (small) set of routers, within a domain, are configured as 348 candidate bootstrap routers. Initially, each of these candidates 349 includes its address in `RP-set' messages. Through a simple election 350 mechanism, a single bootstrap router (BSR) is elected for that domain 351 (see Section 3.6). 353 A set of routers within a domain are configured as candidate RPs (C- 354 RPs); typically these will be the same routers that are configured as 355 C-BSRs. Candidate RPs periodically unicast Candidate-RP-Advertisement 356 messages (C-RP-Advs) to the BSR of that domain. C-RP-Advs include the 357 address of the advertising C-RP, as well as an optional group address 358 and a mask length field, indicating the group prefix(es) for which 359 the candidacy is advertised. The BSR then includes a set of these 360 Candidate-RPs in the RP-Set messages, along with the corresponding 361 group prefixes (see Section 362 3.6.2). RP-Set messages are periodically sent hop-by-hop throughout 363 the domain. 365 Routers receive and store RP-Set messages originated by the BSR. When 366 a DR receives IGMP Host-Membership-Report (or a data packet) from a 367 directly connected host, for a group for which it has no entry, the 368 DR uses a hash function to map the pertinent group to one of the C- 369 RPs whose Group-prefix includes the group (see Section 3.7). The DR 370 then sends a Join/Prune message towards (or unicasts Registers to) 371 that RP. 373 The RP-Set message indicates liveness of the RPs included therein; if 374 an RP is included in the message, then it is tagged as `up' at the 375 routers, while RPs not included in the message are tagged as `down' 376 and removed from the list of RPs over which the hash algorithm acts. 377 Each router continues to use the contents of the most recently 378 received RP-set message until it receives a new RP-set message. 379 _________________________ 380 [*] A domain in this context is a contiguous set of 381 routers that all implement PIM and are configured to 382 operate within a common boundary defined by PIM Multi- 383 cast Border Routers (PMBRs). PMBRs connect each PIM 384 domain to the rest of the internet. 386 2.7 Interoperation with dense mode protocols such as DVMRP 388 In order to interoperate with networks that run dense-mode, 389 broadcast and prune, protocols, such as DVMRP, all packets generated 390 within a PIM-SM region must be pulled down to that region's PIM 391 Multicast Border Routers (PMBRs) and injected (i.e., broadcast) into 392 the DVMRP network. [*] 394 To achieve this capability, a special entry type, referred to as 395 (*,*,RP), must be supported by all PIM routers. For this reason we 396 include details about (*,*,RP) entry handling in this general PIM 397 specification. 399 A data packet will match on a (*,*,RP) entry if there is no more 400 specific entry (such as (S,G) or (*,G)) and the destination group 401 address in the packet maps to the RP listed in the (*,*,RP) entry. In 402 this sense, a (*,*,RP) entry represents an aggregation of all the 403 groups supported by that RP. PMBRs initialize (*,*,RP) state for each 404 RP in the domain's RPset. The (*,*,RP) state causes the PMBRs to send 405 Join/Prune messages toward each of the active RPs in the domain. As a 406 result distribution trees are built that carry all data packets 407 originated within the PIM domain (and sent to the RPs) down to the 408 PMBRs. 410 All PIM routers must be capable of supporting (*,*,RP) state and 411 interpreting associated Join/Prune messages. We describe the handling 412 of (*,*,RP) entries and messages throughout this document. However, 413 detailed PIM Multicast Border Router functions will be specified in a 414 separate interoperability document. 416 2.8 Multicast data packet processing 418 Data packets are processed in a manner similar to existing multicast 419 schemes. A router first performs a longest match on the source and 420 group address in the data packet. A (S,G) entry is matched first if 421 one exists; a (*,G) entry is matched otherwise. If neither state 422 exists, then a (*,*,RP) entry match is attempted as follows: the 423 router hashes on G to identify the RP for group G, and looks for a 424 _________________________ 425 [*] A PMBR is a router that sits at the boundary of a 426 PIM-SM domain and interoperates with other types of 427 multicast routers such as those that run DVMRP. Gen- 428 erally a PMBR would speak both protocols and implement 429 interoperability functions not required by regular PIM 430 routers. 432 (*,*,RP) entry that has this RP address associated with it. If none 433 of the above exists, then the packet is dropped. If a state is 434 matched, the router compares the interface on which the packet 435 arrived to the incoming interface field in the matched forwarding 436 entry. If the iif check fails the packet is dropped, otherwise the 437 packet is forwarded to all interfaces listed in the outgoing 438 interface list. 440 Some special actions are needed to deliver packets continuously while 441 switching from the shared to shortest-path tree. In particular, when 442 a (S,G) entry is matched, incoming packets are forwarded as follows: 444 1 If the SPT-bit is set, then: 446 1 if the incoming interface is the same as a matching 447 (S,G) iif, the packet is forwarded to the oif-list of 448 (S,G). 450 2 if the incoming interface is different than a matching 451 (S,G) iif , the packet is discarded. 453 2 If the SPT-bit is cleared, then: 455 1 if the incoming interface is the same as a matching 456 (S,G) iif, the packet is forwarded to the oif-list of 457 (S,G). In addition, the SPT bit is set for that entry 458 if the incoming interface differs from the incoming 459 interface of the (*,G) or (*,*,RP) entry. 461 2 if the incoming interface is different than a matching 462 (S,G) iif, the incoming interface is tested against a 463 matching (*,G) or (*,*,RP) entry. IF the iif is the 464 same as one of those, the packet is forwarded to the 465 oif-list of the matching entry. 467 3 Otherwise the iif does not match any entry for G and 468 the packet is discarded. 470 Data packets never trigger prunes. However, data packets may 471 trigger actions that in turn trigger prunes. For example, when 472 router B in figure 3 decides to switch to SP-tree at step 3, it 473 creates a (S,G) entry with SPT-bit set to 0. When data packets 474 from S arrive at interface 2 of B, B sets the SPT-bit to 1 475 since the iif for (*,G) is different than that for (S,G). This 476 triggers the sending of prunes towards the RP. 478 2.9 Operation over Multi-access Networks 480 This section describes a few additional protocol mechanisms 481 needed to operate PIM over multi-access networks: Designated 482 Router election, Assert messages to resolve parallel paths, and 483 the Joiner bit to suppress redundant Joins on multi-access 484 networks. 486 2.9.1 Designated router election 488 When there are multiple routers connected to a multi-access 489 network, one of them should be chosen to operate as the 490 designated router (DR) at any point in time. The DR is 491 responsible for sending triggered Join/Prune and Register 492 messages toward the RP [*] 494 A simple designated router (DR) election mechanism is used for 495 both SM and traditional IP multicast routing. 497 Neighboring routers send Query messages to each other. The 498 sender with the largest IP address assumes the role of DR. Each 499 router connected to the multi-access LAN sends the Queries 500 periodically in order to adapt to changes in router status. 502 2.9.2 Parallel paths to a source or the RP--Assert process 504 If a router receives a multicast datagram on a multi-access LAN 505 from a source whose corresponding (S,G) outgoing interface list 506 includes the interface to that LAN, the packet must be a 507 duplicate. In this case a single forwarder must be elected. 508 Using Assert messages addressed to `224.0.0.13' (ALL-PIM-ROUTERS 509 group) on the LAN, upstream routers can resolve which one will 510 act as the forwarder. Downstream routers listen to the Asserts 511 so they know which one was elected, and therefore where to send 512 _________________________ 513 [*] IGMP Queries are sent by a PIMv2 DR if it supports 514 IGMPv1. If a PIMv2 router is using IGMPv2 then Host 515 queries are not sent by the PIMv2 DR but by the IGMP 516 querier. 518 subsequent Joins. Typically this is the same as the downstream 519 router's RPF (Reverse Path Forwarding) neighbor; but there are 520 circumstances where this might not be the case, e.g., when using 521 different unicast protocols. [*] 523 The upstream router elected is the one that has the shortest 524 distance to the source. Therefore, when a packet is received on 525 an outgoing interface a router sends an Assert message on the 526 multi-access LAN indicating what metric it uses to reach the 527 source of the data packet. The router with the smallest 528 numerical metric (with ties broken by highest address) will 529 become the forwarder. All other upstream routers will delete the 530 interface from their outgoing interface list. The downstream 531 routers also do the comparison in case the forwarder is 532 different than the RPF neighbor. 534 Associated with the metric is a metric preference value. This is 535 provided to deal with the case where the upstream routers may 536 run different unicast routing protocols. The numerically smaller 537 metric preference is always preferred. The metric preference 538 should be treated as the high-order part of an assert metric 539 comparison. Therefore, a metric value can be compared with 540 another metric value provided both metric preferences are the 541 same. A metric preference can be assigned per unicast routing 542 protocol and needs to be consistent for all routers on the 543 multi-access network. 545 Asserts are also needed for (*,G) entries since there may be 546 parallel paths from the RP and sources to a multi-access 547 network. When an assert is sent for a (*,G) entry, the first bit 548 in the metric preference (RPT-bit) is always set to 1 to 549 indicate that this path corresponds to the RP tree, and that the 550 match should be done on (*,G) if it exists. Furthermore, the 551 RPT-bit is always cleared for metric preferences that refer to 552 SP-tree entries; this causes an SP-tree path to always look 553 better than an RP-tree path. When the SP-tree and RPtree cross 554 the same LAN, this mechanism eliminates the duplicates that 555 would otherwise be carried over the LAN. 557 In case the packet, or the Assert message, matches on oif for 558 _________________________ 559 [*] The RPF neighbor for a particular source (or RP) is 560 the next-hop router to which packets are forwarded en 561 route to that source (or RP); and therefore is con- 562 sidered a good path via which to accept packets from 563 that source. 565 (*,*,RP) entry, a (*,G) entry is created, and asserts take place 566 as if the matching state were (*,G). 568 The DR may lose the (*,G) Assert process to another router on 569 the LAN if there are multiple paths to the RP through the LAN. 570 From then on, the DR is no longer the last-hop router for local 571 receivers and removes the LAN from its (*,G) oif list. The 572 winning router becomes the last-hop router and is responsible 573 for sending (*,G) join messages to the RP. Asserts are rate 574 limited. 576 2.9.3 Join/Prune suppression 578 If a Join/Prune message arrives and matches on the incoming 579 interface for an existing (S,G), (*,G), or (*,*,RP) entry, and 580 the sender of the Join/Prune has a higher IP address than the 581 recipient of the message, the Joiner-bit in the recipient's 582 multicast routing table entry is cleared to suppress further 583 Join/Prune messages. A timer is set for the Joiner-bit; after it 584 expires the recipient sets the Joiner-bit to resume further 585 periodic Join/Prunes for this entry. The Joiner-bit timer is 586 restarted each time a Join/Prune message is received from a 587 higher-IP-addressed PIM neighbor. 589 2.10 Unicast Routing Changes 591 When unicast routing changes, an RPF check is done on all active 592 (S,G), (*,G) and (*,*,RP) entries, and all affected expected 593 incoming interfaces are updated. In particular, if the new 594 incoming interface appears in the outgoing interface list, it is 595 deleted from the outgoing interface list. The previous incoming 596 interface may be added to the outgoing interface list by a 597 subsequent Join/Prune from downstream. Join/Prune messages 598 received on the current incoming interface are ignored. 599 Join/Prune messages received on new interfaces or existing 600 outgoing interfaces are not ignored. Other outgoing interfaces 601 are left as is until they are explicitly pruned by downstream 602 routers or are timed out due to lack of appropriate Join/Prune 603 messages. If the router has a (S,G) entry with the SPT-bit set, 604 and the updated iif(S,G) does not differ from iif(*,G) or 605 iif(*,*,RP), then the router resets the SPT-bit. 607 The router must send a Join/Prune message with S in the Join 608 list out its new incoming interface to inform upstream routers 609 that it expects multicast datagrams over the interface. It may 610 also send a Join/Prune message with S in the Prune list out the 611 old incoming interface, if the link is operational, to inform 612 upstream routers that this part of the distribution tree is 613 going away. 615 2.11 PIM-SM for Inter-Domain Multicast 617 Future documents will address the use of PIM-SM as a backbone 618 inter-domain multicast routing protocol. Design choices center 619 primarily around the distribution and usage of RP information 620 for wide area, inter-domain groups. 622 2.12 Security 624 All PIM control messages may use [5] to address security 625 concerns. Security mechanisms are likely to be enhanced in the 626 near future. 628 3 Detailed Protocol Description 630 This section describes the protocol operations from the 631 perspective of an individual router implementation. In 632 particular, for each message type we describe how it is 633 generated and processed. 635 3.1 Query 637 Query messages are sent so neighboring routers can discover each 638 other. 640 3.1.1 Sending Queries 642 Query messages are sent periodically between PIM neighbors. By 643 default they are transmitted every 30 seconds. This informs 644 routers what interfaces have PIM neighbors. Query messages are 645 multicast using address 224.0.0.13 (ALL-PIM-ROUTERS group). The 646 packet includes the holdtime for neighbors to keep the 647 information valid. The recommended holdtime is 3 times the query 648 transmission interval. By default the holdtime is 90 seconds. 649 Queries are sent on all types of communication links. 651 3.1.2 Receiving queries 653 When a router receives a Query packet, it stores the IP address 654 for that neighbor, sets the PIM neighbor timer based on the 655 Query holdtime, and determines the Designated Router (DR) for 656 that interface. The highest IP addressed system is elected DR. 657 Each query received causes the DR's address to be updated. 659 When a router that is the active DR receives a query from a new 660 neighbor (i.e., from an IP address that is not yet in the DRs 661 neighbor table), the DR unicasts its most recent RP-set 662 information to the new neighbor. 664 3.1.3 Timing out neighbor entries 666 A periodic process is run to time out PIM neighbors that have 667 not sent queries. If the DR has gone down, a new DR is chosen by 668 scanning all neighbors on the interface and selecting the new DR 669 to be the one with the highest IP address. If an interface has 670 gone down, the router may optionally time out all PIM neighbors 671 associated with the interface. 673 3.2 Join/Prune 675 Join/Prune messages are sent to join or prune a branch off of 676 the multicast distribution tree. A single message contains both 677 a join and prune list, either one of which may be null. Each 678 list contains a set of source addresses, indicating the source- 679 specific trees or shared tree that the router wants to join or 680 prune. 682 3.2.1 Sending Join/Prune Messages 684 Join/Prune messages are merged such that a message sent to a 685 particular upstream neighbor, N, includes all of the current 686 joined and pruned sources that are reached via N; according to 687 unicast routing Join/Prune messages are multicast to all routers 688 on multi-access networks with the target address set to the next 689 hop router towards S or RP. Join/Prune messages are sent 690 periodically. Currently the period is set to 60 seconds. [*] 692 In addition, certain events cause triggered Join/Prune messages 693 to be sent. 695 3.2.1.1 Periodic Join/Prune Messages 697 A router sends a periodic Join/Prune message to each distinct 698 RPF neighbor associated with each (S,G), (*,G) and (*,*,RP) 699 entry. Join/Prune messages are only sent if the RPF neighbor is 700 a PIM neighbor. A periodic Join/Prune message sent to a 701 particular RPF neighbor is constructed as follows: 703 1 Each router determines the RP for a (*,G) entry by using 704 the hash function described. The RP address (with RP and WC 705 bits set) is included in the join list of a periodic 706 Join/Prune message under the following conditions: 708 1 The Join/Prune message is being sent to the RPF 709 neighbor toward the RP for an active (*,G) or (*,*,RP) 710 entry, and 712 _________________________ 713 [*] In the future we will introduce mechanisms to 714 rate-limit this control traffic on a hop by hop basis, 715 in order to avoid excessive overhead on small links. 717 2 The outgoing interface list in the (*,G) or (*,*,RP) 718 entry is non-NULL, or the router is the DR on the same 719 interface as the RPF neighbor. 721 2 A particular source address, S, is included in the join 722 list with the RP and WC bits cleared under the following 723 conditions: 725 1 The Join/Prune message is being sent to the RPF 726 neighbor toward S, and 728 2 There exists an active (S,G) entry with the RPT-bit 729 flag cleared, and 731 3 The oif list in the (S,G) entry is not null. 733 3 A particular source address, S, is included in the prune 734 list with the RP and WC bits cleared under the following 735 conditions: 737 1 The Join/Prune message is being sent to the RPF 738 neighbor toward S, and 740 2 There exists an active (S,G) entry with the RPT-bit 741 flag cleared, and 743 3 The oif list in the (S,G) entry is null. 745 4 A particular source address, S, is included in the prune 746 list with the RPT-bit set and the WC bit cleared under the 747 following conditions: 749 1 The Join/Prune message is being sent to the RPF 750 neighbor toward the RP and there exists a (S,G) entry 751 with the RPT-bit flag set and null oif list, or 753 2 The Join/Prune message is being sent to the RPF 754 neighbor toward the RP, there exists a (S,G) entry 755 with the RPT-bit flag cleared and SPT-bit set, and the 756 incoming interface toward S is different than the 757 incoming interface toward the RP, or 759 3 The Join/Prune message is being sent to the RPF 760 neighbor toward the RP, and there exists a (*,G) entry 761 and (S,G) entry for a directly connected source. 763 5 The RP address (with RP and WC bits set) is included in the 764 prune list if: 766 1 The Join/Prune message is being sent to the RPF 767 neighbor toward the RP and there exists a (*,G) entry 768 with a null oif list (see Section 3.5.2). 770 3.2.1.2 Triggered Join/Prune Messages 772 In addition to periodic messages, the following events will 773 trigger Join/Prune messages (the contents of triggered messages 774 are the same as the periodic, described above): 776 1 Receipt of an IGMP Host-Membership-Report message for a 777 group G will cause building or modifying corresponding 778 (*,G) state, and subsequent triggering of upstream 779 Join/Prune messages as follows: 781 1 If the receiving router does not have a forwarding 782 entry for G the router creates a (*,G) entry, with the 783 interface upon which the IGMP Host-Membership-Report 784 was received included in the oif list. The router 785 sends a Join/Prune message towards the RP with the RP 786 address and RPT-bit and WC-bits set in the join list. 787 A timer is initiated for each interface in the oif 788 list. Or, 790 2 If the (*,G) already exists, the interface upon which 791 the IGMP Host-Membership-Report was received is added 792 to the oif list (if it was not included already) and 793 the timer for that interface is restarted. 795 2 Receipt of a Join/Prune message for (S,G), (*,G) or 796 (*,*,RP) will cause building or modifying corresponding 797 state, and subsequent triggering of upstream Join/Prune 798 messages, in the following cases: 800 1 When there is no current forwarding entry, the RP 801 address included in the Join/Prune message is checked 802 against the local RP-Set information. If it matches, 803 an entry will be created. If the router has no RP-Set 804 information it may discard the message, or optionally 805 use the RP address included in the message. 807 The new entry will in turn trigger an upstream 808 Join/Prune message. 810 2 When the outgoing interface list of (S,G)RPT-bit entry 811 is null, the triggered Join/Prune message will contain 812 S in the prune list. 814 3 Receipt of a packet that matches on a (S,G) entry whose 815 SPT-bit is cleared triggers the following if the packet 816 arrived on the correct incoming interface and there is a 817 (*,G) or (*,*,RP) entry with a different incoming RPF 818 neighbor: a) the router sets the SPT-bit on the (S,G) 819 entry, and b) if the iif of the (S,G) entry is different 820 from the iif of the local (*,G) or (*,*,RP) entries, the 821 router sends a Join/Prune message towards the RP with S and 822 a set RPT-bit in the prune list. 824 4 When a Join/Prune message is received for a group G, the 825 prune list is checked. If it contains a source for which 826 the receiving router has a corresponding active (S,G), 827 (*,G) or (*,*,RP) entry, and whose iif is that on which 828 the Join/Prune was received, then a join for (S,G), (*,G) 829 or (*,*,RP) is triggered to override the prune, 830 respectively. (This is necessary in the case of parallel 831 downstream routers connected to a multi-access network.) 833 5 When the RP fails, the RP will not be included in the RP- 834 Set messages sent to all routers in that domain. This 835 triggers the DRs to send (*,G) Join/Prune messages towards 836 the new RP for the group, as determined by the RP-Set and 837 the hash function [*] 839 We do not trigger prunes onto interfaces for SM groups based on 840 data packets. Data packets that arrive on the wrong incoming 841 interface for an SM group are silently dropped. 843 3.2.1.3 Fragmentation 844 It is possible that a Join/Prune message 845 constructed according to the preceeding rules could exceed the 846 MTU of a network. In this case, the message can undergo semantic 847 fragmentation whereby information corresponding to different 848 groups can be sent in different messages. However, if a 849 Join/Prune message must be fragmented the complete prune list 850 corresponding to a group G must be included in the same 851 Join/Prune message as the associated RP-tree Join for G. 853 3.2.2 Receiving Join/Prune Messages When a router receives a 854 Join/Prune message, it processes it as follows. 856 The receiver of the Join/Prune notes the interface on which the 857 PIM message arrived, call it I. The receiver then checks to see 858 if the Join/Prune message was addressed to the receiving router 859 itself (i.e., the router's address appears in the Unicast 860 Upstream Neighbor Router field of the the Join/Prune message) 861 [*] If the Join/Prune is for this router the following actions 862 are taken. 864 For each Sj in the join list of the Join/Prune message: 866 1 If an address, Sj, in the join list of the Join/Prune 867 messagehas the RPT-bit and WC-bit set, then Sj is the RP 868 address used by the downstream router(s) and the following 869 actions are taken: 871 1 If Sj is not the same as the receiving router's RP 872 mapping for G, the receiving router may ignore the 873 _________________________ 874 [*] As described earlier, PMBRs trigger (*,*,RP) joins 875 towards each RP in the RP-Set. 876 [*] If the router is connected to a multiaccess LAN, 877 the message could be intended for a different router. 879 Join/Prune message with respect to that group entry. 880 If the router does not have any RP-Set information, it 881 may use the address Sj included in the Join/Prune 882 message as the RP for the group. 884 2 If Sj is the same as the receiving router's RP mapping 885 for G, the receiving router adds I to the outgoing 886 interface list of the (*,G) forwarding entry and sets 887 the timer for that interface (if there is no (*,G) 888 entry, the router creates one first). If a (*,*,RP) 889 entry exists, for the RP associated with G, then the 890 oif list of the newly created (*,G) entry is copied 891 from that (*,*,RP) entry. 893 3 For each (Si,G) entry associated with group G, if Si 894 is not included in the prune list, and if I is not the 895 iif then interface I is added to the oif list and 896 the timers are restarted for that interface in each 897 affected entry. If the group address in the Join/Prune 898 message is `*' then every (*,G) and (S,G) entry, whose 899 group address hashes to the RP indicated in the 900 (*,*,RP) Join/Prune message, is updated accordingly 901 [*] 903 4 If the (Si,G) entry has its RPT-bit flag set to 1, and 904 its oif list is the same as the (*,G) oif 905 list, then the (Si,G)RPT-bit entry is deleted, 907 5 The incoming interface is set to the interface used to 908 send unicast packets to the RP in the (*,G) forwarding 909 entry, i.e., RPF interface toward the RP. 911 2 For each address, Sj, in the join list whose RPT-bit and 912 WC-bit are not set, and for which there is no existing 913 (Sj,G) forwarding entry, the router initiates one. 914 [*] 915 _________________________ 916 [*] A `*' in the group field of the Join/Prune is 917 represented by a group address 224.0.0.0 and a group 918 mask length of 4, indicating a (*,*,RP) Join. 919 [*] The router creates a (S,G) entry and copies all 920 1 The outgoing interface for (Sj,G) is set to I. The 921 incoming interface for (Sj,G) is set to the interface 922 used to send unicast packets to Sj (i.e., the RPF 923 neighbor). 925 2 If the interface, I, used to reach Sj, is the same as 926 the outgoing interface being initialized, this 927 represents an error (or a unicast routing change) and 928 the Join/Prune should not be processed. 930 3 For each address, Sj, in the join list of the Join/Prune 931 message, for which there is an existing (Sj,G) forwarding 932 entry, 934 1 If the RPT-bit is not set for Sj listed in the 935 Join/Prune message, but the RPT-bit flag is set on the 936 existing (Sj,G) entry, the router clears the RPT-bit 937 flag on the (Sj,G) entry, sets the incoming interface 938 to point towards Sj for that (Sj,G) entry, and sends a 939 Join/Prune message corresponding to that entry through 940 the new incoming interface; and 942 2 If I is not the same as the existing incoming 943 interface, the router adds I to the list of outgoing 944 interfaces. 946 3 The timer for I is restarted. 948 4 The (Sj,G) entry's SPT bit is cleared until data comes 949 down the shortest path tree. 951 _________________________ 952 outgoing interfaces from the (S,G)RPT-bit entry, if it 953 exists. If there is no (S,G) entry, the oif list is 954 copied from the (*,G) entry; and if there is no (*,G) 955 entry, the oif list is copied from the (*,*,RP) entry, 956 if it exists. In all cases, the iif of the (S,G) entry 957 is always excluded from the oif list. 959 For each Sp in the prune list of the Join/Prune message: 961 1 For each address, Sp, in the prune list whose RPT-bit and 962 WC-bit are cleared: 964 1 If there is an existing (Sp,G) forwarding entry, the 965 router schedules a deletion of I from the list of 966 outgoing interfaces by lowering that oif timer to 5 967 seconds (unless it is already lower). The deletion is 968 not executed until this timer expires, allowing for 969 other downstream routers on a multi-access LAN to 970 override the prune. 972 2 If the router has a current (*,G), or (*,*,RP), 973 forwarding entry, and if the existing (Sp,G) entry has 974 its RPT-bit flag set to 1, then this (Sp,G)RPT-bit 975 entry is maintained (not deleted) even if its outgoing 976 interface list is null. 978 2 For each address, Sp, in the prune list whose RPT-bit is 979 set and whose WC-bit cleared: 981 1 If there is an existing (Sp,G) forwarding entry, the 982 router schedules a deletion of I from the list of 983 outgoing interfaces by lowering that oif timer to 5 984 seconds (unless it is already lower). The deletion is 985 not executed until this timer expires, allowing for 986 other downstream routers on a multi-access LAN to 987 override the prune. 989 2 If the router has a current (*,G), or (*,*,RP), 990 forwarding entry, and if the existing (Sp,G) entry has 991 its RPT-bit flag set to 1, then this (Sp,G)RPT-bit 992 entry is maintained (not deleted) even if its outgoing 993 interface list is null. 995 3 If (*,G), or corresponding (*,*,RP), state exists, but 996 there is no (Sp,G) entry, an (Sp,G)RPT-bit entry is 997 created . The outgoing interface list is copied from 998 the (*,G), or (*,*,RP), entry, with the interface, I, 999 on which the prune was received, is deleted. Packets 1000 from the pruned source, Sp, match on this state and 1001 are not forwarded toward the pruned receivers. 1003 4 If there exists a (Sp,G) entry, with or without the 1004 RPT-bit set, the iif on which the prune was received, 1005 I, is deleted from the oif list, and the entry 1006 timer is restarted. 1008 3 For each address, Sp, in the prune list whose RPT-bit and 1009 WC-bit are both set: 1011 1 If there is an existing (*,G) entry, with Sp as the RP 1012 for G, the router schedules a deletion of I from the 1013 list of outgoing interfaces by lowering that oif timer 1014 to 5 seconds (unless it is already lower). The 1015 deletion is not executed until this timer expires, 1016 allowing for other downstream routers on a multi- 1017 access LAN to override the prune. 1019 2 If the corresponding (*,*,RP) state exists, but there 1020 is no (*,G) entry, a (*,G) entry is created. The 1021 outgoing interface list is copied from (*,*,RP) entry, 1022 with the interface, I, on which the prune was 1023 received, deleted. 1025 3 If there exists a (*,G) entry, the interface on which 1026 the prune was received, I, is deleted from the oif 1027 list, and the entry timer is restarted. 1029 For any new (S,G), (*,G) or (*,*,RP) entry created by an 1030 incoming Join/Prune message, the Joiner-bit is initialized 1031 to 1 and the SPT-bit is cleared. 1033 If the received Join/Prune does not indicate the router as its 1034 target, then if the Join/Prune matches an existing (S,G), (*,G), 1035 or (*,*,RP) entry and the Join/Prune arrived on the iif for 1036 that entry, then the router compares the IP address of the 1037 generator of the Join/Prune, to its own IP address and sets the 1038 Joiner-bit as follows. 1040 1 If its own IP address is higher, the Joiner-bit in the 1041 entry is set. 1043 2 If its own IP address is lower, the Joiner-bit in the entry 1044 is cleared, and the Joiner-bit timer is activated. 1046 After the timer expires the Joiner-bit is set indicating further 1047 periodic Join/Prunes should be sent for this entry. The Joiner- 1048 bit timer is restarted each time a Join/Prune message is 1049 received from a higher-IP-addressed PIM neighbor. 1051 3.3 Register and Register-Stop 1053 When a source first starts sending to a group its packets are 1054 encapsulated in Register messages and sent to the RP. If the 1055 data rate warrants source-specific paths, the RP sets up source 1056 specific state and starts sending (S,G) Join/Prune messages 1057 toward the source, with S in the join list. 1059 3.3.1 Sending Registers and Receiving Register-Stops 1061 Register messages are sent as follows: 1063 1 When a DR receives a packet from a directly connected 1064 source, S [*] : 1066 1 If there is no corresponding (S,G) entry, and the 1067 _________________________ 1068 [*] When a PMBR (e.g., a router that connects the PIM- 1069 SM region to a dense mode region running DVMRP or PIM- 1070 DM) receives a packet from a source in the dense mode 1071 region, the router treats the packet as if it were from 1072 a directly connected source. A separate document will 1073 describe the details of interoperabiity. 1075 router has RP-Set information, the DR creates one with 1076 the Register-bit set to 1 and the RP address set 1077 according to the hash function mapping for the 1078 corresponding group. The Register-bit-timer is 1079 initialized to zero; the Register-bit-timer is non- 1080 zero only when the Register-bit is set to 0. 1082 2 If there is a (S,G) entry in existence, the DR simply 1083 restarts the corresponding S-timer (entry timer). 1085 2 If the new or previously-existing (S,G) entry has the 1086 Register-bit set, the data packet is encapsulated in a 1087 Register message and unicast to the RP for that group. The 1088 data packet is also forwarded according to (S,G) state in 1089 the DR if the oif list is not null; since a receiver may 1090 join the SP-tree while the DR is still registering to the 1091 RP. 1093 3 If the (S,G) entry has the Register-bit cleared, the data 1094 packet is not sent in a Register message, it is just 1095 forwarded according to the (S,G) oif list. 1097 When the DR receives a Register-Stop message it clears the 1098 Register-bit and restarts the Register-bit-timer in the 1099 corresponding (S,G) entry(ies). 1101 When a Register-bit-timer expires, the corresponding entry(ies) 1102 Register-bit is set to 1 to reinstigate encapsulation of data 1103 packets in Register messages. 1105 3.3.2 Receiving Register Messages and Sending Register-Stops 1107 When a router (i.e., the RP) receives a Register message, the 1108 router does the following: 1110 1 Decapsulates the data packet, and checks for a 1111 corresponding (S,G) entry. 1113 1 If a (S,G) entry exists, the packet is forwarded but 1114 the SPT bit is left cleared (0). If the SPT bit is 1, 1115 the packet is dropped, and Register-Stop messages are 1116 triggered. Register-Stops are rate limited. [*] 1118 2 If there is no (S,G) entry, but there is a (*,G) 1119 entry, or a (*,*,RP) entry with the RP corresponding 1120 to G, the packet is forwarded according to that entry. 1122 3 If there is a (*,*,RP) entry but no (*,G) entry, a 1123 (*,G) or (S,G) entry is created and the oif is copied 1124 from the (*,*,RP) entry to the new entry. 1126 4 If there is no G or (*,*,RP) entry corresponding to G, 1127 the packet is dropped, and a Register-Stop is 1128 triggered. 1130 5 A ``Border bit'' bit is added to the Register message, 1131 to facilitate interoperability mechanisms. PMBRs set 1132 this bit when registering for external sources (see 1133 Section 2.7). If the ``Border bit'' is set in the 1134 Register, the RP does the following: 1136 1 If there is no matching (S,G) state, the RP 1137 creates one, with a `PMBR' field. This field 1138 holds the source of the Register (i.e. the outer 1139 IP address of the register packet). The RP 1140 triggers a (S,G) join towards the source of the 1141 data packet, and clears the SPT bit for the (S,G) 1142 entry, else 1144 _________________________ 1145 [*] Register-Stops should be rate limited so that no 1146 more than a few are sent per round trip time. This 1147 prevents a high datarate stream of packets from 1148 triggering a large number of Register-stop messages 1149 between the time that the first packet is received and 1150 the time when the source receives the first Register- 1151 Stop. 1153 2 If the `PMBR' field for the corresponding (S,G) 1154 entry matches the source of the Register packet, 1155 the decapsulated packet is forwarded to the oif 1156 list of that entry, else 1158 3 The packet is dropped, and a Register-stop is 1159 triggered towards the source of the Register. 1161 The (S,G) state timer is restarted by Registers arriving 1162 from that source to that group. 1164 2 If the matching (S,G) or (*,G) state contains a null oif 1165 list, the RP unicasts a Register-Stop message to the source 1166 of the Register message; in the latter case, the source- 1167 address field, within the Register-Stop message, is set to 1168 the wildcard value (all 0's). This message is not processed 1169 by intermediate routers, hence no (S,G) state is 1170 constructed between the RP and the source. 1172 3 If the Register message arrival rate warrants it and there 1173 is no existing (S,G) entry, the RP sets up a (S,G) 1174 forwarding entry with the outgoing interface list, 1175 excluding iif(S,G), copied from the (*,G) outgoing 1176 interface list, its SPT-bit is initialized to 0. If a (*,G) 1177 entry does not exist, but there exists a (*,*,RP) entry 1178 with the RP corresponding to G , the oif list for (S,G) is 1179 copied -excluding the iif- from that (*,*,RP) entry. 1181 A timer is set for the (S,G) entry and this timer is 1182 restarted by receipt of data packets for (S,G). The (S,G) 1183 entry causes the RP to send a Join/Prune message for the 1184 indicated group towards the source of the register message. 1186 If the (S,G) oif list becomes null, Join/Prune messages 1187 will not be sent towards the source, S. 1189 3.4 Multicast Data Packet Forwarding 1191 Processing a multicast data packet involves the following steps: 1193 1 Lookup forwarding state based on a longest match of the 1194 source address, and an exact match of the destination 1195 address in the data packet. If neither S, nor G, find a 1196 longest match entry, and the RP for the packet's 1197 destination group address has a corresponding (*,*,RP) 1198 entry, then the longest match does not require an exact 1199 match on the destination group address. In summary, the 1200 longest match is performed in the following order: (1) 1201 (S,G), (2) (*,G). If neither is matched, then a lookup is 1202 performed on (*,*,RP) entries. 1204 2 If the packet arrived on the interface found in the 1205 matching-entry's iif field, and the oif list is not 1206 null: 1208 1 Forward the packet to the oif list for that entry 1209 and restarted the entry's timer if the matching entry 1210 is (S,G) [*] 1212 2 If the entry is a (S,G) entry with a cleared SPT-bit, 1213 and a (*,G) or associated (*,*,RP) also exists whose 1214 incoming interface is different than that for (S,G), 1215 set the SPT-bit for the (S,G) entry and trigger an 1216 (S,G) RPT-bit prune towards the RP. 1218 3 If the source of the packet is a directly-connected 1219 host and the router is the DR on a multi-access 1220 network, check the Register-bit associated with the 1221 (S,G) entry. If it is set, then the router 1222 encapsulates the data packet in a register message and 1223 sends it to the RP. 1225 This covers the common case of a packet arriving on the RPF 1226 interface to the source or RP and being forwarded to all 1227 joined branches. It also detects when packets arrive on the 1228 SP-tree, and triggers their pruning from the RP-tree. If it 1229 _________________________ 1230 [*] Optionally, the (S,G) timer may be restarted by 1231 periodic checking of the matching packet count. 1233 is the DR for the source, it sends data packets 1234 encapsulated in Registers to the RPs. 1236 3 If the packet matches to an entry but did not arrive on the 1237 interface found in the entry's iif field, check the 1238 SPT-bit of the entry. If the SPT-bit is set, drop the 1239 packet. If the SPT-bit is cleared, then lookup the (*,G), 1240 or (*,*,RP), entry for G. If the packet arrived on the 1241 iif found in (*,G), or the corresponding (*,*,RP), 1242 forward the packet to the oif list of the matching 1243 entry. This covers the case when a data packet matches on a 1244 (S,G) entry for which the SP-tree has not yet been 1245 completely established upstream. 1247 4 If the packet does not match to any entry, but the source 1248 of the data packet is a local, directly-connected host, and 1249 the router is the DR on a multi-access LAN and has RP-Set 1250 information, the DR uses the hash function to determine the 1251 RP associated with the destination group, G. The DR then 1252 checks the Register-bit associated with the local sender 1253 (if there is no such a Register-bit, a new register flag, 1254 associated with the local sender, is created and set), and 1255 encapsulates the data packet in a Register message and 1256 unicasts it to the RP. 1258 5 If the packet does not match to any entry, and it is not a 1259 local host or the router is not the DR, drop the packet. 1261 3.4.1 Data triggered switch to shortest path tree (SP-tree) 1263 Different criteria can be applied to trigger switching over from 1264 the RP-based shared tree to source-specific, shortest path 1265 trees. 1267 One proposed example is to do so based on data rate. For 1268 example, when a (*,G), or corresponding (*,*,RP), entry is 1269 created, a data rate counter may be initiated at the last-hop 1270 routers. The counter is incremented with every data packet 1271 received for directly connected members of an SM group, if the 1272 longest match is (*,G) or (*,*,RP). If and when the data rate 1273 for the group exceeds a certain configured threshold (t1), the 1274 router initiates `source-specific' data rate counters for the 1275 following data packets. Then, each counter for a source, is 1276 incremented when packets matching on (*,G), or (*,*,RP), are 1277 received from that source. If the data rate from the particular 1278 source exceeds a configured threshold (t2), a (S,G) entry is 1279 created and a Join/Prune message is sent towards the source. If 1280 the RPF interface for (S,G) is 1281 not the same as that for (*,G) -or (*,*,RP), then the SPT-bit 1282 is cleared in the (S,G) entry. 1284 Other configured rules may be enforced to cause or prevent 1285 establishment of (S,G) state. 1287 3.5 Assert 1289 Asserts are used to resolve which of the parallel routers 1290 connected to a multi-access LAN is responsible for forwarding 1291 packets onto the LAN. 1293 3.5.1 Sending Asserts 1295 The following Assert rules are provided when a multicast packet 1296 is received on an outgoing multi-access interface of an existing 1297 (S,G) entry: 1299 1 Do unicast routing table lookup on source IP address from 1300 data packet, and send assert on interface for source IP 1301 address in data packet; include metric preference of 1302 routing protocol and metric from routing table lookup. 1304 2 If route is not found, use metric preference of 0x7fffffff 1305 and metric 0xffffffff. 1307 When an assert is sent for a (*,G) entry, the first bit in the 1308 metric preference (the RPT-bit) is set to 1, indicating the data 1309 packet is routed down the RP-tree. 1311 Asserts are rate-limited by the router. 1313 3.5.2 Receiving Asserts 1315 When an assert is received the router performs a longest match 1316 on the source and group address in the assert message. The 1317 router checks the first bit of the metric preference (RPT-bit). 1319 1 If the RPT-bit is set, the router first does a match on 1320 (*,G), or (*,*,RP), entries; if no matching entry is found, 1321 the router matches (S,G) entries. 1323 2 If the RPT-bit is not set in the Assert, the router first 1324 does a match on (S,G) entries; if no matching entry is 1325 found, the router matches (*,G) or (*,*,RP) entries. 1327 3.5.2.1 Receiving Asserts on an entry's outgoing interface 1329 If the interface that received the Assert message is in the 1330 oif list of the matched entry, then this assert should be 1331 processed by this router as follows: 1333 1 If the Assert's RPT-bit is set and the matching entry is 1334 (*,*,RP), the router creates a (*,G) entry. If the Assert's 1335 RPT-bit is cleared and the matching entry is (*,G), or 1336 (*,*,RP), the router creates a (S,G)RPT-bit entry. 1338 2 Compare the metric received in the Assert with the one the 1339 router would have advertised in an assert. The metric 1340 preference should be treated as the high-order part of an 1341 assert metric comparison. If the value in the assert is 1342 less than the router's value, delete the interface from the 1343 entry. If the value is the same, compare IP addresses, if 1344 the routers address is less than the assert sender, delete 1345 the interface. 1347 3 If the router has won the election and there are directly 1348 connected members on the multi-access LAN, the router keeps 1349 the interface in its outgoing interface list. It acts as 1350 the forwarder for the LAN. 1352 4 If the router won the election but there are no directly 1353 connected members on the multi-access LAN, the router 1354 schedules to delete the interface. The LAN might be a stub 1355 LAN with no members (and no downstream routers). If no 1356 subsequent Join/Prunes are received, the router deletes the 1357 interface from the outgoing interface list; otherwise it 1358 keeps the interface in its outgoing interface and acts as 1359 the forwarder for the LAN. 1361 The winning router should send out an assert message including 1362 its own metric to that outgoing interface. This will cause other 1363 routers on the LAN to prune that interface from their forwarding 1364 entries. 1366 3.5.2.2 Receiving Asserts on an entry's incoming interface 1368 If the Assert arrived on the incoming interface of an existing 1369 (S,G), (*,G), or (*,*,RP) entry, the Assert is processed as 1370 follows. If the Assert message does not match the entry, 1371 exactly, it is ignored; i.e, longest-match is not used in this 1372 case. If the Assert message does match exactly, then: 1374 1 Downstream routers will select the upstream router with the 1375 smallest metric as their RPF neighbor. If two metrics are 1376 the same, the highest IP address is chosen to break the 1377 tie. [*] 1379 2 If the downstream routers have downstream members, they 1380 must schedule a join to inform the upstream router that 1381 packets should be forwarded on the multi-access network. 1382 This will cause the upstream forwarder to cancel its 1383 _________________________ 1384 [*] This is important so that downstream routers send 1385 subsequent Joins/Prunes (in SM) to the correct neigh- 1386 bor. An Assert timer is initiated when changing the RPF 1387 neighbor to the Assert winner. When the timer expires 1388 the router resets its RPF neighbor according to its un- 1389 icast routing tables to capture failures of the Assert 1390 winner. 1392 scheduled deletion of the interface. 1394 3.6 Candidate-RP-Advertisements and RP-Set messages 1396 Candidate-RP-Advertisements (C-RP-Advs) are periodic PIM 1397 messages unicast by those routers that are configured as 1398 Candidate-RPs (C-RPs). 1400 RP-Set messages are periodic PIM messages originated by the 1401 Bootstrap router (BSR) within a domain, and forwarded hop-by-hop 1402 to distribute the current RP-set to all routers in that domain. 1404 The RP-Set messages also support a simple mechanism by which the 1405 Candidate BSR (C-BSR) with the highest BSR-priority and IP 1406 address (referred to as the preferred BSR) is elected as the BSR 1407 for the domain [*] Sections 3.6.2 and 3.6.3 describe the 1408 combined function of RP-Set messages as the vehicle for BSR 1409 election and RP-Set distribution. 1411 _________________________ 1412 [*] We recommend that each router configured as a C-RP 1413 also be configured as a C-BSR. 1415 3.6.1 Sending Candidate-RP-Advertisements 1417 C-RPs periodically unicast C-RP-Advs to the BSR for that domain. 1418 The interval for sending these messages is subject to local 1419 configuration at the C-RP. A recommended default value is 60 1420 seconds. 1422 Candidate-RP-Advertisements carry group address and group mask 1423 fields. This enables the advertising router to limit the 1424 advertisement to certain prefixes or scopes of groups. The 1425 advertising router may enforce this scope acceptance when 1426 receiving Registers or Join/Prune messages. 1428 3.6.2 Receiving C-RP-Advs and Originating RP-Set 1430 Upon receiving a C-RP-Adv, a router does the following: 1432 1 If the router is not the elected BSR, it ignores the 1433 message, else 1435 2 The BSR adds the RP address to its local pool of candidate 1436 RPs, according to the associated group prefix(es) in the 1437 C-RP-Adv message [*] The BSR may override the prefix 1438 indicated in a C-RP-Adv. 1440 The BSR keeps an RP-timer per RP in its local RP-set. The RP- 1441 timer is initialized to the holdtime in the RP's C-RP-Adv. When 1442 the timer expires, the corresponding RP is removed from the RP- 1443 set. The RP-timer is restarted by the C-RP-Advs from the 1444 corresponding RP. 1446 The BSR also keeps an RP-Set timer to send RP-Set messages 1447 periodically. In particular, when the RP-Set timer expires, the 1448 BSR originates an RP-Set message on each of its PIM interfaces. 1449 The message is sent with a TTL of 1 to the `ALL-PIM-ROUTERS' 1450 group. In steady state, the BSR originates RP-Set messages every 1451 60 seconds. At startup, the RP-Set timer is initialized to 180 1452 seconds, causing the first RP-Set message to be originated after 1453 180 seconds, when/if the timer expires. For timer details see 1454 Section 3.6.3. A DR unicasts an RP-Set message to new PIM 1455 neighbors starting up, after receiving their Query messages. 1456 _________________________ 1457 [*] The BSR may apply a local policy to limit the 1458 number of Candidate RPs included in the RP-Set message. 1460 (since after DR election the new neighbor may become the new 1461 DR.) 1463 The RP-Set message is subdivided into sets of group-prefix,RP- 1464 Count,RP-addresses. The format of the RP-Set message allows 1465 `semantic fragmentation', if the length of the original RP-Set 1466 message exceeds the packet maximum boundaries (see Section 4). 1467 However, we recommend against configuring a large number of 1468 routers as C-RPs, to reduce the semantic fragmentation required. 1470 3.6.3 Receiving and Forwarding RP-Set 1472 Each router keeps an RP-Set timer, initialized to 180 seconds at 1473 startup. 1475 When a router receives RP-Set message sent to `ALL-PIM-ROUTERS' 1476 group, it performs the following: 1478 1 If the message was not sent by the RPF neighbor towards the 1479 BSR address included, the message is dropped. Else 1481 2 If the included BSR is not preferred over, and not equal 1482 to, the currently active BSR: 1484 1 If the RP-Set timer is not yet expired, or if the 1485 receiving router is a C-BSR, then the RP-Set message 1486 is dropped. Else 1488 2 The RP-Set timer has expired and the receiving router 1489 is not a C-BSR, so the receiving router stores the 1490 RP-Set and BSR address and priority found in the 1491 message, and restarts the timer with its maximum 1492 value. The RP-Set message is then forwarded out all 1493 PIM interfaces, excluding the one over which the 1494 message arrived, to `ALL-PIM-ROUTERS' group, with a 1495 TTL of 1. 1497 3 If the RP-Set message includes a BSR address that is 1498 preferred over, or equal to, the currently active BSR, the 1499 router resets its RP-Set timer to 180 seconds, and stores 1500 the BSR address and RP-Set information. The RP-Set message 1501 is then forwarded out all PIM interfaces, excluding the one 1502 over which the message arrived, to `ALL-PIM-ROUTERS' group, 1503 with a TTL of 1. 1505 4 If the receiving router has no current RP set information 1506 and the RP-set was unicast to it from a directly connected 1507 neighbor, the router stores the information as its new RP- 1508 set. This covers the startup condition when a newly booted 1509 router obtains the RP-Set and BSR address from its DR. 1511 When a router receives a new RP-Set it checks if each of the RPs 1512 referred to by existing state (i.e., by (*,G), (*,*,RP), or 1513 (S,G)RPT-bit entries) is in the new RP-Set. If an RP is not in 1514 the new RP-set, that RP is considered unreachable and the hash 1515 algorithm (see below) is re-performed for each group with 1516 locally active state that previously hashed to that RP. This 1517 will cause those groups to be distributed among the remaining 1518 RPs. When the new RP-Set contains a new RP, the value of the new 1519 RP is calculated for each group covered by that C-RP's Group- 1520 prefix. Any group for which the new RP's value is greater than 1521 the previously active RP's value is switched over to the new RP. 1523 3.7 Hash Function 1525 The hash function is used by all routers within a domain, to map 1526 a group to one of the C-RPs from the RP-Set. For a particular 1527 group, G, the hash function uses only those C-RPs whose Group- 1528 prefix covers G. The algorithm takes as input the group address, 1529 and the addresses of the Candidate RPs, and gives as output one 1530 RP address to be used. 1532 The protocol requires that all routers hash to the same RP 1533 within a domain (except for transients). The following hash 1534 function must be used in each router: 1536 1 For each candidate RP address Ci in the Candidate-RP- 1537 Set, whose Group-prefix covers G, compute a value: 1538 Value(G,M,Ci) = 1539 1103515245 ((1103515245 (G&M)+12345) XOR Ci)+ 12345 mod 2^31 1540 where M is a hash-mask included in RP-Set messages. 1541 This hash-mask allows a small number of 1542 consecutive groups (e.g., 4) to always hash to the same RP. 1543 For instance, hierarchically-encoded data can be sent on 1544 consecutive group addresses to get the same delay and 1545 fate-sharing characteristics. 1547 In standard C, this corresponds to: 1549 srand(G & M); 1550 srand(rand() ^ Ci); 1551 value = rand(); 1553 2 The candidate with the highest resulting value is then 1554 chosen as the RP for that group, and its identity and hash 1555 value are stored with the entry created. 1557 Ties between C-RPs having the same hash value, are broken 1558 in advantage of the highest address. 1560 The hash function algorithm is invoked by a DR, upon reception 1561 of a packet, or IGMP Host-Membership-Report, for a group, for 1562 which the DR has no entry. It is invoked by any router that has 1563 (*,*,RP) state when a packet is received for which there is no 1564 corresponding (S,G) or (*,G) entry. Furthermore, the hash 1565 function is invoked by all routers upon receiving a Join/Prune 1566 message with WC-bit set. 1568 3.8 Processing Timer Events 1570 In this subsection, we enumerate all timers that have been 1571 discussed or implied. Since some critical timer events are not 1572 associated with the receipt or sending of messages, they are not 1573 fully covered by earlier subsections. 1575 Timers may either count up or count down. If they count up then 1576 expiration means that the timer has reached its configured 1577 maximum value. If they count down then expiration means that the 1578 timer has reached zero. 1580 In many cases, the values for timers come from Holdtime fields 1581 in PIM control messages, in which case the default values used 1582 in these Holdtime fields are shown in the tables below. 1583 Otherwise, the default value used when setting the timer is 1584 shown. In general, the default timeout value for state 1585 information is three times the refresh period. For example, 1586 Queries refresh Neighbor state and the default Query-timer 1587 period is 30 seconds, so a default Neighbor-timer duration of 90 1588 seconds is included in the Holdtime field of the Queries. 1590 In this version of the spec we suggest particular numerical 1591 timer settings. A future version of the specification will 1592 specify a mechanism for timers to be set as a function of the 1593 outgoing link bandwidth. 1595 3.8.1 Timers related to tree maintenance 1597 Each (S,G), (*,G), and (*,*,RP) entry has multiple timers 1598 associated with it: one for each interface in the outgoing 1599 interface list, one for the multicast routing entry itself, and 1600 one for the Joiner-bit. Each (S,G) and (*,G) entry also has an 1601 Assert timer and an Assert-rate-limit timer. In addition, DR's 1602 have a Register-bit-timer for each (S,G) entry and every router 1603 has a single Join/Prune timer. 1605 Because some of the outgoing interfaces in an (S,G) entry are 1606 copied from the (*,G) outgoing interface list, they may not have 1607 explicit (S,G) join messages from some of the downstream routers 1608 (i.e., where members are joining to the (*,G) tree only). Thus, 1609 when a timer is reset for an outgoing interface listed in a 1610 (*,G) entry, the timers are reset for that interface in each 1611 existing (S,G) entry whose oif list contains that interface [*] 1612 The same rule applies to (*,G) and (S,G) entries when resetting 1613 an oif timer on a (*,*,RP) entry. 1615 _________________________ 1616 [*] If there are sources in the prune list of the (*,G) 1617 join, then the timers for the arriving interface will 1618 first be reset for those sources, and then this inter- 1619 face will be deleted from these same entries; producing 1620 a correct result, even though the updating of the ti- 1621 mers was unnecessary. An implementation could optimize 1622 this by checking the prune list before processing the 1623 join list. 1625 Timer DefVal Notes 1627 Joiner-bit 90 Started : When Joiner bit is cleared 1628 per route entry Reset by: Receiving Join from higher-IP neighbor on iif 1629 Action : Set Joiner bit 1631 Join/Prune 60 Started : When booting 1632 Reset by: Nothing 1633 Action : Send Join/Prune to each RPF neighbor, restart timer 1635 oif 180 Started : When adding oif to oiflist 1636 per (*,*,RP) oif Restarted by: Receiving (*,*,RP) Join on that iface 1637 Action : Remove oif from oiflist 1639 oif 180 Started : When adding oif to oiflist 1640 per (*,G) oif Restarted by: Receiving (*,G) Join or IGMP 1641 Host-Membership-Report for G on that iface, or 1642 restartedting oif timer in (*,*,RP). 1643 Action : Remove oif from oiflist 1645 oif 180 Started : When adding oif to oiflist 1646 per (S,G) oif Restarted by: Receiving (S,G) Join on that 1647 iface, or restartedting oif timer in (*,G) or 1648 (*,*,RP). 1649 Action : Remove oif from oiflist 1651 (*,*,RP) entry 180 Started : When entry is created 1652 per (*,*,RP) Restarted by: Restartedting timer on any oif 1653 Action : Delete entry 1655 (*,G) entry 180 Started : When entry is created 1656 per (*,G) Restarted by: Receiving (*,G) prune, 1657 restarting timer on any oif, or receiving an 1658 Assert with RPT-bit set. 1659 Action : Delete entry and any associated 1660 (S,G)RPT-bit entries 1662 (S,G) entry 180 Started : When entry is created 1663 aka S-timer Restarted by: Forwarding data packet, 1664 per (S,G) receiving Register, receiving (S,G)RPT-bit 1665 prune, restarting timer on any oif, 1666 or receiving an Assert without RPT-bit set. 1667 Action : Delete entry 1669 Register-bit 60 Started : When Register bit is cleared by 1670 per (S,G) receiving a Register-Stop 1671 Restarted by: Receiving Register-Stop 1672 Action : Set Register bit 1674 Assert 180 Started : Receiving an Assert where the 1675 per (S,G) upstream RPF neighbor is not your unicast RPF 1676 and (*,G) neighbor. 1677 Restarted by: Receiving an Assert where the 1678 upstream RPF neighbor is not your unicast 1679 RPF neighbor. 1680 Action : Change RPF neighbor to unicast RPF neighbor 1682 Assert-Rate-limit 5 Started : When an Assert is sent 1683 per (S,G) Restarted by: Nothing 1684 and (*,G) Action : Allow asserts to be triggered by 1685 data packets 1687 3.8.2 Timers relating to neighbor discovery 1689 Timer DefVal Notes 1691 Query 30 Started : When booting 1692 Restarted by: Nothing 1693 Action : Send Query on all ifaces, restart timer 1695 Neighbor 90 Started : When receive first Query from neighbor 1696 per neighbor Restarted by: When receive subsequent Queries 1697 Action : Delete neighbor entry 1699 3.8.3 Timers relating to RP information 1701 Timer DefVal Notes 1703 C-RP-Adv 60 Started : When booting if you're a Cand-RP 1704 Restarted by: Nothing 1705 Action : Send C-RP-Adv, restart C-RP-Adv timer 1707 RP 180 Started : When adding an RP to the RP-Set if 1708 per RP you are BSR 1709 Restarted by: Receiving C-RP-Adv 1710 Action : Remove RP from RP-Set 1712 RP-Set 180/60 Started : Set to 180 when booting if 1713 you're a C-BSR 1714 Restarted by: Restarted to 180 when receive 1715 RP-Set from preferred router if you're a C-BSR 1716 Action : Send RP-Set and restart timer to 60 secs 1718 3.9 Summary of flags used 1720 Following is a summary of all the flags used in our scheme. 1722 Bit Used in Definition 1724 Border Register Register is coming from a PIM multicast border router. 1725 Joiner Route entry Periodic Join/Prunes should be sent for this entry. 1726 Register (S,G) entry Encapsulate packets from directly connected 1727 sources in Register messages unicast to the RP 1728 for that group. 1729 RP Route entry Entry represents state on the RP-tree. 1730 RP Join/Prune Join is associated with the shared tree and therefore 1731 the Join/Prune message is propagated along the RP-tree. 1732 RP Assert The data packet was routed down the shared tree; thus, 1733 the path indicated corresponds to the RP tree. 1734 SPT (S,G) entry Packets have arrived on the iif towards S, 1735 and the iif is different from the (*,G) iif. 1736 WC Join Included address is an RP and the receiver expects to 1737 receive packets from all sources via this (shared tree) 1738 path. Thus, the Join/Prune applies to a (*,G) entry. 1739 WC Route entry Wildcard entry; if there is no more specific match for 1740 a particular source, packets will be forwarded according 1741 to this entry. 1743 3.10 Security 1745 Editors Note: this section is to be completed. 1747 All PIM control messages may use [5] to address security 1748 concerns. 1750 4 Packet Formats 1752 This section describes the details of the packet formats for PIM 1753 control messages. 1755 All PIM control messages have protocol number 103. 1757 Basically, PIM messages are either unicast (e.g. Registers and 1758 Register-Stop), or multicast hop-by-hop to `ALL-PIM-ROUTERS' 1759 group `224.0.0.13' (e.g. Join/Prune, Asserts, etc.). 1761 0 1 2 3 1762 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 1763 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1764 |PIM Ver| Type | Addr length | Checksum | 1765 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1767 PIM Ver 1768 PIM Version number is 2. 1770 Type Types for specific PIM messages. PIM Types are: 1772 0 = Query 1773 1 = Register 1774 2 = Register-Stop 1775 3 = Join/Prune 1776 4 = RP-Set 1777 5 = Assert 1778 6 = Graft (used in PIM-DM only) 1779 7 = Graft-Ack (used in PIM-DM only) 1780 8 = Candidate-RP-Advertisement 1782 Addr length 1783 Address length in bytes. Throughout this section this 1784 would indicate the number of bytes in the Address field of 1785 an address, including unicast and group addresses. 1787 Checksum 1788 The checksum is the 16-bit one's complement of the one's 1789 complement sum of the entire PIM message, (excluding the 1790 data portion in the Register message). For computing the 1791 checksum, the checksum field is zeroed. 1793 4.1 Encoded Source and Group Address formats 1795 1 Unicast address: Only the address is included. The length 1796 of the unicast address in bytes is specified in the `Addr 1797 length' field in the header. 1799 2 Encoded-Group-Address: Takes the following format: 1801 0 1 2 3 1802 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 1803 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1804 | Reserved | Mask Len | Group multicast Address ... | 1805 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1806 | ...Group multicast Address ...| 1807 +-+-+-+-+-+-+-+-+-+-+~+~+~+~+~+~+ 1809 Reserved 1810 Transmitted as zero. Ignored upon receipt. 1812 Mask Len 1813 The Mask length is 8 bits. The value is the number of 1814 contiguous bits left justified used as a mask which 1815 describes the address. It is less than or equal to 1816 Addr length * 8. If the message is sent for a single 1817 group then the Mask length should equal Addr length * 1818 8 (i.e. 32 for IPv4 and 128 for IPv6). 1820 Group multicast Address 1821 contains the group address, and has number of bytes 1822 equal to that specified in the Addr length field. 1824 3 Encoded-Source-Address: Takes the following format: 1826 0 1 2 3 1827 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 1828 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1829 | Rsrvd |S|W|R| Mask Len | Source Address ... | 1830 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1831 | ... Source Address | 1832 +-+-+-+-+-+-+-+-+-+-+-+-+-+~+~+-+ 1834 Reserved 1835 Transmitted as zero, ignored on receipt. 1837 S,W,R See Section 4.5 for details. 1839 Mask Length 1840 Mask length is 8 bits. The value is the number of 1841 contiguous bits left justified used as a mask which 1842 describes the address. The mask length must be less 1843 than or equal to Addr Length * 8. If the message is 1844 sent for a single source then the Mask length should 1845 equal Addr length * 8. In version 2 of PIM, it is 1846 strongly recommended that this field be set to 32 for 1847 IPv4. 1849 Source Address 1850 The address length is indicated from the Addr length 1851 field at the beginning of the header. For IPv4, the 1852 address length is 4 octets. 1854 4.2 Query Message 1856 It is sent periodically by routers on all interfaces. 1858 0 1 2 3 1859 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 1860 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1861 |PIM Ver| Type | Addr length | Checksum | 1862 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1863 | Reserved | Holdtime | 1864 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1866 PIM Version, Type, Addr length, Checksum 1867 Described above. 1869 Reserved 1870 Transmitted as zero, ignored on receipt. 1872 Holdtime 1873 The amount of time a receiver should keep the neighbor 1874 reachable, in seconds. 1876 4.3 Register Message 1878 It is sent by the Designated Router (DR) to the RP when a 1879 multicast packet needs to be transmitted on the RP-tree. Source 1880 IP address is set to the address of the DR, destination IP 1881 address is to the RP's address. 1883 0 1 2 3 1884 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 1885 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1886 |PIM Ver| Type | Addr length | Checksum | 1887 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1888 |B| Reserved | 1889 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1890 | | 1891 Multicast data packet 1892 | | 1893 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1895 PIM Version, Type, Addr length, Checksum 1896 Described above. Note that the checksum for Registers 1897 is done only on the PIM header, excluding the data packet 1898 portion. 1900 B The Border bit. Set to zero by all DRs. Set to `1' by the 1901 PIM Multicast Border Routers, when registering for external 1902 sources. 1904 Multicast data packet 1905 The original packet sent by the source. 1907 4.4 Register-Stop Message 1909 A Register-Stop is unicast from the RP to the sender of the 1910 Register message. Source IP address is the address to which the 1911 register was addressed. Destination IP address is the source 1912 address of the register message. 1914 0 1 2 3 1915 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 1916 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1917 |PIM Ver| Type | Addr length | Checksum | 1918 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1919 | Encoded-Group Address | 1920 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1921 | Unicast-Source Address | 1922 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1924 PIM Version, Type, Addr length, Checksum 1925 Described above. 1927 Encoded-Group Address 1928 Format described above. Note that for Register-Stops the 1929 Mask Len field should contain Addr length * 8 (32 for 1930 IPv4), if the message is sent for a single group. 1932 Unicast-Source Address 1933 IP host address of source from multicast data packet in 1934 register. The length of this field in bytes is specified in 1935 the Addr length field. A special wild card value (0.0.0.0), 1936 can be used to indicate any source. 1938 4.5 Join/Prune Message 1940 It is sent by routers towards upstream sources and RPs. A join 1941 creates forwarding state and a prune destroys forwarding state. 1942 Joins are sent to build shared trees (RP trees) or source trees 1943 (SPT). Prunes are sent to prune source trees when members leave 1944 groups as well as sources that do not use the shared tree. 1946 0 1 2 3 1947 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 1948 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1949 |PIM Ver| Type | Addr length | Checksum | 1950 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1951 | Unicast-Upstream Neighbor Address | 1952 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1953 | Reserved | Num groups | Holdtime | 1954 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1955 | Encoded-Multicast Group Address-1 | 1956 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1957 | Number of Joined Sources | Number of Pruned Sources | 1958 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1959 | Encoded-Joined Source Address-1 | 1960 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1961 | . | 1962 | . | 1963 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1964 | Encoded-Joined Source Address-n | 1965 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1966 | Encoded-Pruned Source Address-1 | 1967 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1968 | . | 1969 | . | 1970 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1971 | Encoded-Pruned Source Address-n | 1972 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1973 | . | 1974 | . | 1975 | . | 1976 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1977 | Encoded-Multicast Group Address-n | 1978 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1979 | Number of Joined Sources | Number of Pruned Sources | 1980 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1981 | Encoded-Joined Source Address-1 | 1982 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1983 | . | 1984 | . | 1985 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1986 | Encoded-Joined Source Address-n | 1987 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1988 | Encoded-Pruned Source Address-1 | 1989 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1990 | . | 1991 | . | 1992 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1993 | Encoded-Pruned Source Address-n | 1994 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1996 PIM Version, Type, Addr length, Checksum 1997 Described above. 1999 Upstream Neighbor Address 2000 The IP address of the RPF or upstream neighbor. 2002 Reserved 2003 Transmitted as zero, ignored on receipt. 2005 Holdtime 2006 The amount of time a receiver should keep the Join/Prune 2007 state alive, in seconds. 2009 Number of Groups 2010 The number of multicast group sets contained in the 2011 message. 2013 Encoded-Multicast group address 2014 For format description see Section 2015 4.1. A wild card group in the (*,*,RP) join is represented 2016 by a 224.0.0.0 in the group address field and `4' in the 2017 mask length field. A (*,*,RP) join also has the WC-bit and 2018 the RPT-bit set. 2020 Number of Joined Sources 2021 Number of join source addresses listed for a given group. 2023 Join Source Address-1 .. n 2024 This list contains the sources that the sending router 2025 will forward multicast datagrams for if received on the 2026 interface this message is sent on. 2028 See format section 4.1. The fields explanation for the 2029 Encoded-Source-Address format follows: 2031 Reserved 2032 Described above. 2034 S The Sparse bit is a 1 bit value, set to 1 for PIM-SM. 2035 It is used for PIM v.1 compatability. 2037 W The WC bit is a 1 bit value. If 1, the join or prune 2038 applies to the (*,G) or (*,*,RP) entry. If 0, the join 2039 or prune applies to the (S,G) entry where S is Source 2040 Address. Joins and prunes sent towards the RP should 2041 have this bit set. 2043 R The RPT-bit is a 1 bit value. If 1, the information 2044 about (S,G) is sent towards the RP. If 0, the 2045 information should be sent about (S,G) toward S, where 2046 S is Source Address. 2048 Mask Length, Source Address 2049 Described above. 2051 Represented in the form of < WC-bit >< RPT-bit >< 2052 Mask length >< Source address>: 2054 A source address could be a host IP address : 2056 < 0 >< 0 >< 32 >< 192.1.1.17 > 2058 A source address could be the RP's IP address : 2060 < 1 >< 1 >< 32 >< 131.108.13.111 > 2062 A source address could be a subnet address to prune from 2063 the RP-tree : 2065 < 0 >< 1 >< 28 >< 192.1.1.16 > 2067 A source address could be a general aggregate : 2069 < 0 >< 0 >< 16 >< 192.1.0.0 > 2071 Number of Pruned Sources 2072 Number of prune source addresses listed for a group. 2074 Prune Source Address-1 .. n 2075 This list contains the sources that the sending router 2076 does not want to forward multicast datagrams for when 2077 received on the interface this message is sent on [*] 2078 _________________________ 2079 [*] If the Join/Prune message boundary exceeds the max- 2080 4.6 RP-Set 2082 The RP-Set messages are multicast to `ALL-PIM-ROUTERS' group, 2083 out all interfaces having PIM neighbors (excluding the one over 2084 which the message was received). RP-Set messages are sent with 2085 TTL value of 1. RP-Set messages originate at the BSR, and are 2086 forwarded by intermediate routers. 2088 RP-Set message is divided up into `semantic fragments', if the 2089 original message exceeds the maximum packet size boundaries. 2091 The semantics of a single `fragment' is given below: 2093 _________________________ 2094 imum packet size, then the join and prune lists for the 2095 same group must be included in the same packet. 2097 0 1 2 3 2098 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 2099 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2100 |PIM Ver| Type | Addr length | Checksum | 2101 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2102 | Fragment Tag | Hash Mask len | BSR-priority | 2103 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2104 | Unicast-BSR-Address | 2105 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2106 | Encoded-Group Address-1 | 2107 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2108 | RP-Count-1 | Frag RP-Cnt-1 | Reserved | 2109 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2110 | Unicast-RP-Address-1 | 2111 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2112 | . | 2113 | . | 2114 | . | 2115 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2116 | Unicast-RP-Address-m | 2117 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2118 | . | 2119 | . | 2120 | . | 2121 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2122 | Encoded-Group Address-n | 2123 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2124 | RP-Count-m | Frag RP-Cnt-m | Reserved | 2125 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2126 | Unicast-RP-Address-1 | 2127 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2128 | . | 2129 | . | 2130 | . | 2131 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2132 | Unicast-RP-Address-m | 2133 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2135 PIM Version, Type, Addr length, Checksum 2136 Described above. 2138 Fragment Tag 2139 A randomly generated number, acts to distinguish the 2140 fragments belonging to different RP-Set messages; fragments 2141 belonging to same RP-Set message carry the same `Fragment 2142 Tag'. 2144 Hash Mask len 2145 The length (in bits) of the mask to use in the hash 2146 function. For IPv4 we recommend a value of 30. For IPv6 we 2147 recommend a value of 126. 2149 BSR-priority 2150 Contains the BSR priority value of the included BSR. This 2151 field is considered as a high order byte when comparing BSR 2152 addresses. 2154 Unicast-BSR-Address 2155 The IP address of the bootstrap router for the domain. The 2156 length of this field in bytes is specified in Addr length. 2158 Encoded-Group Address-1..n 2159 The group prefix (address and mask) with which the 2160 Candidate RPs are associated. Format previously described. 2162 RP-Count-1..n 2163 The number of Candidate RP addresses included in the whole 2164 RP-Set message for the corresponding group prefix [*] 2166 Frag RP-Cnt-1..m 2167 The number of Candidate RP addresses included in this 2168 fragment of the RP-Set message, for the corresponding group 2169 prefix. The `Frag RP-Cnt' field facilitates parsing of the 2170 RP-Set for a given group prefix, when carried over more 2171 than one fragment. 2173 Unicast-RP-address-1..m 2174 The address of the Candidate RPs, for the corresponding 2175 _________________________ 2176 [*] A router does not replace its old RP-Set for a 2177 given group prefix until/unless it receives `RP-Count' 2178 addresses for that prefix; the addresses could be car- 2179 ried over several fragments. If only part of the RP-Set 2180 for a given group prefix was received, the router dis- 2181 cards it, without updating that specific group prefix's 2182 RP-Set. 2184 group prefix. The length of this field in bytes is 2185 specified in Addr length. 2187 4.7 Assert Message 2189 The Assert message is sent when a multicast data packet is 2190 received on an outgoing interface corresponding to the (S,G) or 2191 (*,G) associated with the source. 2193 0 1 2 3 2194 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 2195 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2196 |PIM Ver| Type | Addr length | Checksum | 2197 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2198 | Encoded-Group Address | 2199 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2200 | Unicast-Source Address | 2201 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2202 |R| Metric Preference | 2203 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2204 | Metric | 2205 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2207 PIM Version, Type, Addr length, Checksum 2208 Described above. 2210 Encoded-Group Address 2211 The group address to which the data packet was addressed, 2212 and which triggered the Assert. Format previously 2213 described. 2215 Unicast-Source Address 2216 Source IP address from IP multicast datagram that 2217 triggered the Assert packet to be sent. The length of this 2218 field in bytes is specified in Addr length. 2220 R RPT-bit is a 1 bit value. If the IP multicast datagram 2221 that triggered the Assert packet is routed down the RP 2222 tree, then the RPT-bit is 1; if the IP multicast datagram 2223 is routed down the SPT, it is 0. 2225 Metric Preference 2226 Preference value assigned to the unicast routing protocol 2227 that provided the route to Host address. 2229 Metric The unicast routing table metric. The metric is in units 2230 applicable to the unicast routing protocol used. 2232 4.8 Graft Message 2234 Used in dense-mode. Refer to PIM dense mode specification. 2236 4.9 Graft-Ack Message 2238 Used in dense-mode. Refer to PIM dense mode specification. 2240 4.10 Candidate-RP-Advertisement 2242 Candidate-RP-Advertisements are periodically unicast from the 2243 C-RPs to the BSR. 2245 0 1 2 3 2246 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 2247 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2248 |PIM Ver| Type | Addr length | Checksum | 2249 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2250 | Prefix-Cnt | Reserved | Holdtime | 2251 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2252 | Unicast-RP-Address | 2253 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2254 | Encoded-Group Address-1 | 2255 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2256 | . | 2257 | . | 2258 | . | 2259 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2260 | Encoded-Group Address-n | 2261 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2263 PIM Version, Type, Addr length, Checksum 2264 Described above. 2266 Prefix-Cnt 2267 The number of encoded group addresses included in the 2268 message; indicating the group prefixes for which the C-RP 2269 is advertising. A Prefix-Cnt of `0' implies a prefix of 2270 224.0.0.0 with mask length of 4; i.e. all multicast groups. 2271 If the C-RP is not configured with Group-prefix 2272 information, the C-RP puts a default value of `0' in this 2273 field. 2275 Holdtime 2276 The amount of time the advertisement is valid. This field 2277 allows advertisements to be aged out. 2279 Unicast-RP-Address 2280 The address of the interface to advertise as a Candidate 2281 RP. The length of this field in bytes is specified in Addr 2282 length. 2284 Encoded-Group Address-1..n 2285 The group prefixes for which the C-RP is advertising. 2286 Format previously described. 2288 5 Appendix I: Major Changes and Updates to the Spec 2290 This appendix populates the major changes in the specification 2291 document as compared to `draft-ietf-idmr-pim-spec-01.ps,txt'. 2293 5.1 Major Changes 2295 List of changes since March '96 IETF: 2297 1. (*,*,RP) Joins state and data forwarding check; replaces (*,G- 2298 Prefix) Joins state for interoperability. (*,G) negative cache 2299 introduced for the (*,*,RP) state supporting mechanisms. 2301 2. Semantic fragmentation for the RP-Set message. 2303 List of changes incurred since version 1 of the spec.: 2305 1. Proposal and refinement of bootstrap router (BSR) election 2306 mechanisms 2308 2. Introduction of hash functions for Group to RP mapping 2310 3. New RP-liveness indication mechanisms based upon the the 2311 Bootstrap Router (BSR) and the RP-Set messages. 2313 4. Removal of reachability messages, RP reports and multiple RPs 2314 per group. 2316 5.2 Packet Format Changes 2318 Packet Format incurred updates to accommodate different address 2319 lengths, and address aggregation. 2321 1 The `Addr length' field was added to the PIM fixed header 2322 to specify the address length in bytes of the underlying 2323 protocol, see section 4. 2325 2 The Encoded source and group address formats were 2326 introduced, with the use of a `Mask length' field to allow 2327 aggregation, section 4.1. 2329 3 Packet formats are no longer IGMP messages; rather PIM 2330 messages. 2332 PIM message types and formats were also modified: 2334 [ Note: most changes were made to the May 95 version, unless 2335 otherwise specified]. 2337 1 Obsolete messages: 2339 (a) Register-Ack [Feb. 96] 2341 (b) Poll and Poll Response [Feb. 96] 2343 (c) RP-Reachability [Feb. 96] 2345 (d) RPlist-Mapping [Feb. 96] 2347 2 New messages: 2349 (a) Candidate-RP-Advertisement [change made in October 95] 2350 RP-Set [Feb. 96] 2352 3 Modified messages: 2354 (a) Join/Prune [Feb. 96] 2356 (b) Register [Feb. 96] 2358 (c) Register-Stop [Feb. 96] 2360 6 Acknowledgments 2362 Tony Ballardie, Scott Brim, Jon Crowcroft, Bill Fenner, Paul 2363 Francis, Joel Halpern, Horst Hodel, Polly Huang, Stephen 2364 Ostrowski, and Lixia Zhang provided detailed comments on 2365 previous drafts. The authors of [6] and membership of the IDMR 2366 WG provided many of the motivating ideas for this work and 2367 useful feedback on design details. 2369 This work was supported by the National Science Foundation, 2370 ARPA, cisco Systems and Sun Microsystems. 2372 References 2374 1. S.Deering, D.Estrin, D.Farinacci, V.Jacobson, C.Liu, L.Wei, 2375 P.Sharma, and A.Helmy. Protocol independent multicast (pim) : 2376 Motivation and architecture. 2377 Internet Draft, May 1995. 2379 2. S.Deering, D.Estrin, D.Farinacci, V.Jacobson, C.Liu, and L.Wei. 2380 The pim architecture for wide-area multicast routing. 2381 ACM Transactions on Networks, April 1996. 2383 3. D.Estrin, D.Farinacci, V.Jacobson, C.Liu, L.Wei, P.Sharma, and 2384 A.Helmy. Protocol independent multicast-dense mode (pim-dm) : 2385 Protocol specification. Internet Draft, November 1995. 2387 4. S.Deering. Host extensions for ip multicasting, aug 1989. 2388 RFC1112. 2390 5. R.Atkinson. Security architecture for the internet protocol, 2391 August 1995. RFC-1825. 2393 6. A.J. Ballardie, P.F. Francis, and J.Crowcroft. Core based trees. 2394 In Proceedings of the ACM SIGCOMM, San Francisco, 1993.