idnits 2.17.1 draft-ietf-mospf-prunes-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Cannot find the required boilerplate sections (Copyright, IPR, etc.) in this document. Expected boilerplate is as follows today (2024-04-23) 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. == No 'Intended status' indicated for this document; assuming Proposed Standard Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an Introduction section. ** 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.) ** There are 278 instances of lines with control characters in the document. Miscellaneous warnings: ---------------------------------------------------------------------------- -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (December 1998) is 9261 days in the past. Is this intentional? 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 331 looks like a reference -- Missing reference section? '3' on line 337 looks like a reference -- Missing reference section? '5' on line 344 looks like a reference -- Missing reference section? '2' on line 334 looks like a reference -- Missing reference section? '4' on line 341 looks like a reference -- Missing reference section? 'OSPF' on line 402 looks like a reference Summary: 9 errors (**), 0 flaws (~~), 1 warning (==), 8 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group J. Moy 3 Internet Draft Ascend Communications, Inc. 4 Expiration Date: May 1999 December 1998 5 File name: draft-ietf-mospf-prunes-00.txt 7 MOSPF Prunes 9 Status of this Memo 11 This document is an Internet-Draft. Internet-Drafts are working 12 documents of the Internet Engineering Task Force (IETF), its areas, 13 and its working groups. Note that other groups may also distribute 14 working documents as Internet-Drafts. 16 Internet-Drafts are draft documents valid for a maximum of six 17 months and may be updated, replaced, or obsoleted by other documents 18 at any time. It is inappropriate to use Internet- Drafts as 19 reference material or to cite them other than as "work in progress." 21 To view the entire list of current Internet-Drafts, please check the 22 "1id-abstracts.txt" listing contained in the Internet-Drafts Shadow 23 Directories on ftp.is.co.za (Africa), ftp.nordu.net (Northern 24 Europe), ftp.nis.garr.it (Southern Europe), munnari.oz.au 26 (Pacific Rim), ftp.ietf.org (US East Coast), or ftp.isi.edu (US West 27 Coast). 29 Abstract 31 MOSPF is a link-state multicast routing protocol, based on OSPF. 32 Inside a single OSPF area, the delivery of multicast datagrams is 33 restricted to group members only, by propagating the location of 34 group members through group-membership-LSAs. However, group 35 membership is not propagated across area and/or AS boundaries, 36 relying instead on so-called wild-card multicast receivers. This 37 means that in some cases multicast datagrams are transmitted further 38 than necessary, wasting link and processor resources in the process. 40 This document defines a way to prune these excess branches off the 41 MOSPF delivery tree, using a new Prune-LSA. In concept these are 42 similar to the prunes employed by the DVMRP protocol. However, to 43 reuse the reliability mechanisms present in the base OSPF protocol, 44 MOSPF prunes are implemented as local-scope Opaque-LSAs. As a 45 result, inter-area and inter-AS multicast datagrams are forwarded by 46 MOSPF using the broadcast-and-prune strategy employed by DVMRP. 48 Please send comments to mospf@gated.cornell.edu. 50 Table of Contents 52 1 Problem Statement ...................................... 3 53 1.1 The Pruning Solution ................................... 3 54 2 Protocol Specification ................................. 5 55 2.1 Prune Semantics and Syntax ............................. 5 56 2.2 Effect of Prunes on the routing calculation ............ 5 57 2.3 When to originate prunes ............................... 6 58 2.4 Prune maintenance ...................................... 7 59 2.5 Receiving Prunes ....................................... 7 60 3 Discussion ............................................. 8 61 15 References ............................................. 9 62 A The Prune-LSA ......................................... 10 63 Security Considerations ............................... 11 64 Author's Address ...................................... 11 65 1. Problem Statement 67 When the MOSPF protocol is employed in an hierarchical fashion, 68 either using OSPF areas or by attaching the MOSPF domain into a 69 large multicast routing system, such as the MBONE, a tradeoff is 70 made between the distribution of group membership and the forwarding 71 of multicast datagrams. Rather than distribute the group membership 72 down the hierarchy, multicast datagrams are forwarded up the 73 hierarchy until they reach a router that has the required group 74 member location information. Unfortunately, this means that the 75 multicast datagrams are often forwarded further than absolutely 76 necessary. 78 Let us use as an example the area configuration displayed in Figure 79 4 of the MOSPF specification [1], and reproduced here as Figure 1. 80 We modify that example in two ways. First, assume that Network N3 is 81 a non-broadcast network (NBMA mode) rather than a broadcast network. 82 Second, assume that the two ASBRs, Routers RT5 and RT7, are both 83 capable of forwarding multicast datagrams to other Autonomous 84 Systems, but that only RT5 wishes to flood datagrams specifying a 85 Network N1 source and Destination Group Mb. 87 Suppose that a host on Network N1 transmits a multicast datagram to 88 multicast group Mb. Router RT1 receives the datagram, and since N3 89 is a non-broadcast network, forwards separate copies to RT2 90 (destined for the Group Mb member on Network N2), and to the two 91 wild-card multicast receivers in Area 1: RT3 and RT4. However, RT3 92 simply discards the packet, since it isn't on the delivery tree to 93 any Mb members. RT4 on the other hand forwards the datagram to RT5. 94 RT5 then forwards the datagram out of the Autonomous System, and 95 also on to the wild-card multicast receiver RT7, which also simply 96 discards the datagram. 98 The transmissions to Routers RT3 and RT7 end up being unnecessary, 99 simply consuming network bandwidth and router processor resources. 100 This problem must be fixed before employing a MOSPF domain as a 101 transit domain with the MBONE. 103 1.1. The Pruning Solution 105 The solution is to prune back the excess branches of the 106 multicast delivery tree, similar to the pruning employed by the 107 DVMRP protocol [3]. In the example above, Router RT3 sends a 108 prune back to RT1, notifying RT1 that it should no longer 109 forward matching datagrams to RT3. Similarly, RT7 sends a prune 110 back to RT5. 112 .................................. 113 . + . 114 . | 3+---+ +--+ . N12 N14 115 . N1|--|RT1|\1 |H4| . \ N13 / 116 . _| +---+ \ /+--+ . 8\ |8/8 117 . | + \ ____/ . \|/ 118 . +--+ +--+ / \ 1+---+8. 8+---+6 119 . |Mb| |Mb| * N3 *---|RT4|------|RT5|--------+ 120 . +--+ /+--+ \____/ +---+ . +---+ | 121 . + / | . |7 | 122 . | 3+---+ / | . | | 123 . N2|--|RT2|/1 |1 . |6 | 124 . __| +---+ +---+8 . 6+---+ | 125 . | + |RT3|--------------|RT6| | 126 . +--+ +--+ +---+ +--+. +---+ | 127 . |Ma| |H3|_ |2 _|H2|. Ia|7 | 128 . +--+ +--+ \ | / +--+. | | 129 . +---------+ . | | 130 .Area 1 N4 . | | 131 .................................. | | 132 ................................ | | 133 . N11 . | | 134 . +---------+ . | | 135 . | \ . | | N12 136 . |3 +--+ . | |6 2/ 137 . +---+ |Ma| . | +---+/ 138 . |RT9| +--+ . | |RT7|---N15 139 . +---+ ....... | +---+ 9 140 . |1 .. + ...|..........|1........ 141 . _|__ .. | Ib|5 __|_ +--+. 142 . / \ 1+----+2.. | 3+----+1 / \--|Ma|. 143 . * N9 *------|RT11|----|---|RT10|---* N6 * +--+. 144 . \____/ +----+ .. | +----+ \____/ . 145 . | !*******|*****! | . 146 . |1 Virtual + Link |1 . 147 . +--+ 10+----+ ..N8 +---+ . 148 . |H1|-----|RT12| .. |RT8| . 149 . +--+SLIP +----+ .. +---+ +--+. 150 . |2 .. |4 _|H5|. 151 . | .. | / +--+. 152 . +---------+ .. +--------+ . 153 . N10 Area 3..Area 2 N7 . 154 ............................................................. 156 Figure 1: A sample MOSPF area configuration 157 Prunes are implemented as LSAs, called Prune-LSAs. Implementing 158 them as LSAs yields reliability through OSPF's standard reliable 159 flooding mechanism. Since Prune-LSAs are only forwarded a single 160 hop, they are implemented as link-local Opaque-LSAs (see Section 161 2.1 and Appendix A). 163 Branches pruned from the delivery tree are grafted back on when 164 the network topology changes (see Section 2.4). Grafting is 165 accomplished simply by flushing (prematurely aging) the Prune- 166 LSAs. 168 2. Protocol Specification 170 The following sections describe MOSPF's pruning operation in detail. 171 This includes the format of the Prune-LSA, its effect on the MOSPF 172 routing calculation, when to generate Prune-LSAs, and when they 173 should be flushed (deleted). 175 2.1. Prune Semantics and Syntax 177 When a MOSPF router originates a Prune-LSA, it is saying that 178 the router does not want to receive any multicast datagrams 179 matching a given source prefix and destination multicast group. 180 Prune-LSAs are link-local Opaque-LSAs [5] with Opaque type field 181 set to 5. The 12-byte body of the Prune-LSA specifies the source 182 prefix (as net and mask) and Destination Group. For more 183 details, see Appendix A. 185 2.2. Effect of Prunes on the routing calculation 187 The presence of Prune-LSAs can cause the labelling of certain 188 vertices to be ignored during the multicast routing calculation 189 (Section 12.2 of [1]). 191 In particular, the following modifications are made to the MOSPF 192 routing calculation for a source prefix SourceNet and 193 Destination Group G: 195 o An extra field, called the "Pruned" field, is added to the 196 vertex data structure in Section 12.1. It can attain either 197 of the values TRUE or FALSE, and is always initialized to 198 FALSE. 200 o If a vertex has "Pruned" set to TRUE, any labelling with 201 group membership is ignored in Section 12.2.5 of [1]. 203 o In Step 5d of Section 12.2 in [1], where a vertex W on the 204 candidate list is modified, W's "Pruned" field is set to 205 TRUE if and only if one of the following conditions hold: 207 o W's parent vertex V has the "Pruned" field set to TRUE. 209 o W is a router immediately downstream from the 210 calculating router (i.e., either V is the calculating 211 router or a network immediately downstream from the 212 calculating router), and W has originated a Prune-LSA 213 for Group G and a source prefix which is either equal to 214 SourceNet or less specific than SourceNet (the latter 215 handles source aggregation at area boundaries). Being a 216 link-local LSA, the Prune-LSA is associated with a 217 particular interface on the calculating router, and this 218 interface must also be equal to either W's 219 AssociatedInterface/Neighbor (see Section 12.1 of [1]) 220 or an interface to a point-to-point link fully adjacent 221 to W. 223 Encountering pruned vertices during the routing calculation may 224 cause the calculating router itself to originate a Prune-LSA for 225 SourceNet and G; see Section 2.3 for details. 227 2.3. When to originate prunes 229 A prune-LSA is originated by Router RTX if, at the time of 230 creating a multicast cache entry, the multicast cache entry for 231 a given source prefix and destination group contains no 232 downstream interfaces or neighbors, but upstream routers believe 233 that Router RTX is on the delivery path for the multicast 234 datagram. 236 Consider for example the network in Figure 1. For a datagram 237 with Source on Network N1 and Destination Group Mb, Router RT3 238 originates a Prune-LSA because it has no downstream interfaces 239 or neighbors, but RT1 thinks RT3 is on the multicast delivery 240 tree due to it's wild-card status. Likewise, RT7 originates a 241 Prune-LSA for Source N1 and Destination Group Mb. However, if a 242 Host on Network N11 send a multicast datagram to Group Ma, RT12 243 does NOT originate a Prune-LSA. While RT12 receives the 244 datagram, and calculates a multicast cache entry without 245 downstream interfaces or neighbors, it knows that RT9 does not 246 really consider RT12 to be on the multicast delivery path, and 247 that it is only getting the datagram because Network N9 is a 248 broadcast network. 250 To be precise, a router originates a Prune-LSA at the time of 251 creating a multicast cache entry if the following conditions all 252 apply: 254 (1) The cache entry has a valid upstream node, and it is not the 255 placeholder EXTERNAL. 257 (2) The cache entry has no downstream interfaces or neighbors. 259 (3) One of the following conditions holds: 261 o The calculating router has declared itself a wild-card 262 multicast receiver in the area containing the cache's 263 entry's upstream node. 265 o During the multicast routing calculation for the given 266 cache entry (See Section 2.2), one or more downstream 267 vertices have been pruned due to the presence of Prune- 268 LSAs. 270 When a Prune-LSA is originated, it specifies the cache entry's 271 source network and destination multicast group, and is flooded 272 with local-scope out the interface to the upstream node. In the 273 previous example, RT3 floods its Prune-LSA onto Network N3, and 274 RT7 floods its Prune-LSA to RT5. When two routers are attached 275 via multiple point-to-point links, it is possible that there are 276 multiple interfaces to the upstream node (see Section 12.2 of 277 [1]). In this case, the Prune-LSA is flooded out any one of the 278 interfaces to the upstream node. 280 The usual rules for OSPF [2] LSA origination apply. In 281 particular, Prune-LSAs should be refreshed every LSRefreshTime 282 period, unless the Prune-LSA is originated with the DoNotAge bit 283 [4] set. In the latter case, the refresh rate is totally up to 284 the Prune-LSA originator. 286 2.4. Prune maintenance 288 When the network topology changes, pruned branches should be 289 restored to the multicast delivery tree. This is accomplished as 290 follows. When a cache entry is deleted (reasons for deleting 291 cache entries are listed in Section 13 of [1]), any locally 292 originated Prune-LSA associated with the cache entry (i.e., 293 having the same source prefix and destination group) is also 294 flushed (prematurely aged). 296 2.5. Receiving Prunes 298 When a Prune-LSA is received, certain multicast calculations 299 must be redone. Suppose a Prune-LSA is received for source 300 prefix SP and multicast group G. For each multicast cache 301 entries specifying G and a source prefix which are equal to SP 302 or more specific than SP (again, to handle source aggregation at 303 area boundaries): 305 o If the Prune-LSA's LS age field is not equal to MaxAge, 306 and the Prune-LSA is received on one of the cache 307 entry's downstream interfaces/neighbors, the cache entry 308 is deleted. 310 o If the Prune-LSA's LS age field is equal to MaxAge 311 (i.e., it's a graft), and the downstream 312 interface/neighbor associated with the Prune-LSA had 313 been pruned according to Section 2.2, the cache entry is 314 deleted. 316 Deleted cache entries will be rebuilt when the next matching 317 multicast datagrams are received. 319 3. Discussion 321 On multi-access networks (either broadcast, NBMA or Point-to- 322 MultiPoint), Prune-LSAs are flooded to more routers than they need 323 to be. They only need be sent to the single upstream router. 325 This document does not specify sufficient functionality to handle to 326 source-specific joins and leaves proposed for IGMPv3, although it is 327 a start. 329 4. References 331 [1] Moy, J., "Multicast Extensions to OSPF", , Ascend Communications, Inc., August 1998. 334 [2] Moy, J., "OSPF Version 2", STD 54, RFC 2328, Ascend 335 Communications, Inc., April 1998. 337 [3] Pusateri, T., "Distance Vector Multicast Routing Protocol", 338 , Juniper Networks, August 339 1998. 341 [4] Moy, J., "Extending OSPF to Support Demand Circuits", RFC 1793, 342 Cascade, April 1995. 344 [5] Coltun, R., "The OSPF Opaque LSA Option", RFC 2370, FORE 345 Systems, July 1998. 347 A. The Prune-LSA 349 Prune-LSAs are implemented as link-local Opaque-LSAs (LS type 9), 350 with subtype (Opaque type) equal to 5. A separate Opaque-LSA is 351 originated for each source prefix and destination group combination 352 that the router wishes to prune. The Prune-LSA is then flooded out 353 the interface connecting to the upstream node for the given source 354 prefix and destination group combination. See Section 2 for more 355 information concerning the origination, processing and flushing of 356 Prune-LSAs. 358 0 1 2 3 359 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 360 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 361 | LS age | Options | 9 | 362 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 363 | 5 | Prune ID | 364 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 365 | Advertising Router | 366 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 367 | LS sequence number | 368 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 369 | LS checksum | length | 370 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 371 | Source net | 372 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 373 | Source mask | 374 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 375 | Destination Group | 376 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 378 The Prune-LSA 380 The Prune-LSA consists of the standard 20-byte link state header 381 (see Section A.4.1 of [OSPF]) followed by the source prefix and 382 destination group specification. Special field definitions within 383 the Prune-LSA are as follows: 385 o Prune ID. A 24-bit integer uniquely identifying each prune 386 currently originated by the router. 388 o Source net, Source mask. Describes the source prefix. 390 o Destination Group. The Class D group address which is pruned for 391 the specified source prefix. 393 Security Considerations 395 MOSPF uses the authentication mechanisms supplied by the base OSPF 396 protocol. All OSPF protocol exchanges are authenticated. OSPF 397 supports multiple types of authentication; the type of 398 authentication in use can be configured on a per network segment 399 basis. One of OSPF's authentication types, namely the Cryptographic 400 authentication option, is believed to be secure against passive 401 attacks and provide significant protection against active attacks. 402 For more information, see [OSPF]. 404 Author's Address 406 John Moy 407 Ascend Communications, Inc. 408 1 Robbins Road 409 Westford, MA 01886 410 Phone: 978-952-1367 411 Fax: 978-392-2075 412 Email: jmoy@casc.com 414 This document expires in May 1999.