Network Working Group J. Moy Internet Draft Ascend Communications, Inc. Expiration Date: May 1999 December 1998 File name: draft-ietf-mospf-prunes-00.txt MOSPF Prunes Status of this Memo This document is an Internet-Draft. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet- Drafts as reference material or to cite them other than as "work in progress." To view the entire list of current Internet-Drafts, please check the "1id-abstracts.txt" listing contained in the Internet-Drafts Shadow Directories on ftp.is.co.za (Africa), ftp.nordu.net (Northern Europe), ftp.nis.garr.it (Southern Europe), munnari.oz.au (Pacific Rim), ftp.ietf.org (US East Coast), or ftp.isi.edu (US West Coast). Abstract MOSPF is a link-state multicast routing protocol, based on OSPF. Inside a single OSPF area, the delivery of multicast datagrams is restricted to group members only, by propagating the location of group members through group-membership-LSAs. However, group membership is not propagated across area and/or AS boundaries, relying instead on so-called wild-card multicast receivers. This means that in some cases multicast datagrams are transmitted further than necessary, wasting link and processor resources in the process. This document defines a way to prune these excess branches off the MOSPF delivery tree, using a new Prune-LSA. In concept these are similar to the prunes employed by the DVMRP protocol. However, to reuse the reliability mechanisms present in the base OSPF protocol, MOSPF prunes are implemented as local-scope Opaque-LSAs. As a result, inter-area and inter-AS multicast datagrams are forwarded by MOSPF using the broadcast-and-prune strategy employed by DVMRP. Moy [Page 1] Internet Draft MOSPF Prunes December 1998 Please send comments to mospf@gated.cornell.edu. Table of Contents 1 Problem Statement ...................................... 3 1.1 The Pruning Solution ................................... 3 2 Protocol Specification ................................. 5 2.1 Prune Semantics and Syntax ............................. 5 2.2 Effect of Prunes on the routing calculation ............ 5 2.3 When to originate prunes ............................... 6 2.4 Prune maintenance ...................................... 7 2.5 Receiving Prunes ....................................... 7 3 Discussion ............................................. 8 15 References ............................................. 9 A The Prune-LSA ......................................... 10 Security Considerations ............................... 11 Author's Address ...................................... 11 Moy [Page 2] Internet Draft MOSPF Prunes December 1998 1. Problem Statement When the MOSPF protocol is employed in an hierarchical fashion, either using OSPF areas or by attaching the MOSPF domain into a large multicast routing system, such as the MBONE, a tradeoff is made between the distribution of group membership and the forwarding of multicast datagrams. Rather than distribute the group membership down the hierarchy, multicast datagrams are forwarded up the hierarchy until they reach a router that has the required group member location information. Unfortunately, this means that the multicast datagrams are often forwarded further than absolutely necessary. Let us use as an example the area configuration displayed in Figure 4 of the MOSPF specification [1], and reproduced here as Figure 1. We modify that example in two ways. First, assume that Network N3 is a non-broadcast network (NBMA mode) rather than a broadcast network. Second, assume that the two ASBRs, Routers RT5 and RT7, are both capable of forwarding multicast datagrams to other Autonomous Systems, but that only RT5 wishes to flood datagrams specifying a Network N1 source and Destination Group Mb. Suppose that a host on Network N1 transmits a multicast datagram to multicast group Mb. Router RT1 receives the datagram, and since N3 is a non-broadcast network, forwards separate copies to RT2 (destined for the Group Mb member on Network N2), and to the two wild-card multicast receivers in Area 1: RT3 and RT4. However, RT3 simply discards the packet, since it isn't on the delivery tree to any Mb members. RT4 on the other hand forwards the datagram to RT5. RT5 then forwards the datagram out of the Autonomous System, and also on to the wild-card multicast receiver RT7, which also simply discards the datagram. The transmissions to Routers RT3 and RT7 end up being unnecessary, simply consuming network bandwidth and router processor resources. This problem must be fixed before employing a MOSPF domain as a transit domain with the MBONE. 1.1. The Pruning Solution The solution is to prune back the excess branches of the multicast delivery tree, similar to the pruning employed by the DVMRP protocol [3]. In the example above, Router RT3 sends a prune back to RT1, notifying RT1 that it should no longer forward matching datagrams to RT3. Similarly, RT7 sends a prune back to RT5. Moy [Page 3] Internet Draft MOSPF Prunes December 1998 .................................. . + . . | 3+---+ +--+ . N12 N14 . N1|--|RT1|\1 |H4| . \ N13 / . _| +---+ \ /+--+ . 8\ |8/8 . | + \ ____/ . \|/ . +--+ +--+ / \ 1+---+8. 8+---+6 . |Mb| |Mb| * N3 *---|RT4|------|RT5|--------+ . +--+ /+--+ \____/ +---+ . +---+ | . + / | . |7 | . | 3+---+ / | . | | . N2|--|RT2|/1 |1 . |6 | . __| +---+ +---+8 . 6+---+ | . | + |RT3|--------------|RT6| | . +--+ +--+ +---+ +--+. +---+ | . |Ma| |H3|_ |2 _|H2|. Ia|7 | . +--+ +--+ \ | / +--+. | | . +---------+ . | | .Area 1 N4 . | | .................................. | | ................................ | | . N11 . | | . +---------+ . | | . | \ . | | N12 . |3 +--+ . | |6 2/ . +---+ |Ma| . | +---+/ . |RT9| +--+ . | |RT7|---N15 . +---+ ....... | +---+ 9 . |1 .. + ...|..........|1........ . _|__ .. | Ib|5 __|_ +--+. . / \ 1+----+2.. | 3+----+1 / \--|Ma|. . * N9 *------|RT11|----|---|RT10|---* N6 * +--+. . \____/ +----+ .. | +----+ \____/ . . | !*******|*****! | . . |1 Virtual + Link |1 . . +--+ 10+----+ ..N8 +---+ . . |H1|-----|RT12| .. |RT8| . . +--+SLIP +----+ .. +---+ +--+. . |2 .. |4 _|H5|. . | .. | / +--+. . +---------+ .. +--------+ . . N10 Area 3..Area 2 N7 . ............................................................. Figure 1: A sample MOSPF area configuration Moy [Page 4] Internet Draft MOSPF Prunes December 1998 Prunes are implemented as LSAs, called Prune-LSAs. Implementing them as LSAs yields reliability through OSPF's standard reliable flooding mechanism. Since Prune-LSAs are only forwarded a single hop, they are implemented as link-local Opaque-LSAs (see Section 2.1 and Appendix A). Branches pruned from the delivery tree are grafted back on when the network topology changes (see Section 2.4). Grafting is accomplished simply by flushing (prematurely aging) the Prune- LSAs. 2. Protocol Specification The following sections describe MOSPF's pruning operation in detail. This includes the format of the Prune-LSA, its effect on the MOSPF routing calculation, when to generate Prune-LSAs, and when they should be flushed (deleted). 2.1. Prune Semantics and Syntax When a MOSPF router originates a Prune-LSA, it is saying that the router does not want to receive any multicast datagrams matching a given source prefix and destination multicast group. Prune-LSAs are link-local Opaque-LSAs [5] with Opaque type field set to 5. The 12-byte body of the Prune-LSA specifies the source prefix (as net and mask) and Destination Group. For more details, see Appendix A. 2.2. Effect of Prunes on the routing calculation The presence of Prune-LSAs can cause the labelling of certain vertices to be ignored during the multicast routing calculation (Section 12.2 of [1]). In particular, the following modifications are made to the MOSPF routing calculation for a source prefix SourceNet and Destination Group G: o An extra field, called the "Pruned" field, is added to the vertex data structure in Section 12.1. It can attain either of the values TRUE or FALSE, and is always initialized to FALSE. o If a vertex has "Pruned" set to TRUE, any labelling with group membership is ignored in Section 12.2.5 of [1]. o In Step 5d of Section 12.2 in [1], where a vertex W on the candidate list is modified, W's "Pruned" field is set to Moy [Page 5] Internet Draft MOSPF Prunes December 1998 TRUE if and only if one of the following conditions hold: o W's parent vertex V has the "Pruned" field set to TRUE. o W is a router immediately downstream from the calculating router (i.e., either V is the calculating router or a network immediately downstream from the calculating router), and W has originated a Prune-LSA for Group G and a source prefix which is either equal to SourceNet or less specific than SourceNet (the latter handles source aggregation at area boundaries). Being a link-local LSA, the Prune-LSA is associated with a particular interface on the calculating router, and this interface must also be equal to either W's AssociatedInterface/Neighbor (see Section 12.1 of [1]) or an interface to a point-to-point link fully adjacent to W. Encountering pruned vertices during the routing calculation may cause the calculating router itself to originate a Prune-LSA for SourceNet and G; see Section 2.3 for details. 2.3. When to originate prunes A prune-LSA is originated by Router RTX if, at the time of creating a multicast cache entry, the multicast cache entry for a given source prefix and destination group contains no downstream interfaces or neighbors, but upstream routers believe that Router RTX is on the delivery path for the multicast datagram. Consider for example the network in Figure 1. For a datagram with Source on Network N1 and Destination Group Mb, Router RT3 originates a Prune-LSA because it has no downstream interfaces or neighbors, but RT1 thinks RT3 is on the multicast delivery tree due to it's wild-card status. Likewise, RT7 originates a Prune-LSA for Source N1 and Destination Group Mb. However, if a Host on Network N11 send a multicast datagram to Group Ma, RT12 does NOT originate a Prune-LSA. While RT12 receives the datagram, and calculates a multicast cache entry without downstream interfaces or neighbors, it knows that RT9 does not really consider RT12 to be on the multicast delivery path, and that it is only getting the datagram because Network N9 is a broadcast network. To be precise, a router originates a Prune-LSA at the time of creating a multicast cache entry if the following conditions all apply: Moy [Page 6] Internet Draft MOSPF Prunes December 1998 (1) The cache entry has a valid upstream node, and it is not the placeholder EXTERNAL. (2) The cache entry has no downstream interfaces or neighbors. (3) One of the following conditions holds: o The calculating router has declared itself a wild-card multicast receiver in the area containing the cache's entry's upstream node. o During the multicast routing calculation for the given cache entry (See Section 2.2), one or more downstream vertices have been pruned due to the presence of Prune- LSAs. When a Prune-LSA is originated, it specifies the cache entry's source network and destination multicast group, and is flooded with local-scope out the interface to the upstream node. In the previous example, RT3 floods its Prune-LSA onto Network N3, and RT7 floods its Prune-LSA to RT5. When two routers are attached via multiple point-to-point links, it is possible that there are multiple interfaces to the upstream node (see Section 12.2 of [1]). In this case, the Prune-LSA is flooded out any one of the interfaces to the upstream node. The usual rules for OSPF [2] LSA origination apply. In particular, Prune-LSAs should be refreshed every LSRefreshTime period, unless the Prune-LSA is originated with the DoNotAge bit [4] set. In the latter case, the refresh rate is totally up to the Prune-LSA originator. 2.4. Prune maintenance When the network topology changes, pruned branches should be restored to the multicast delivery tree. This is accomplished as follows. When a cache entry is deleted (reasons for deleting cache entries are listed in Section 13 of [1]), any locally originated Prune-LSA associated with the cache entry (i.e., having the same source prefix and destination group) is also flushed (prematurely aged). 2.5. Receiving Prunes When a Prune-LSA is received, certain multicast calculations must be redone. Suppose a Prune-LSA is received for source prefix SP and multicast group G. For each multicast cache entries specifying G and a source prefix which are equal to SP Moy [Page 7] Internet Draft MOSPF Prunes December 1998 or more specific than SP (again, to handle source aggregation at area boundaries): o If the Prune-LSA's LS age field is not equal to MaxAge, and the Prune-LSA is received on one of the cache entry's downstream interfaces/neighbors, the cache entry is deleted. o If the Prune-LSA's LS age field is equal to MaxAge (i.e., it's a graft), and the downstream interface/neighbor associated with the Prune-LSA had been pruned according to Section 2.2, the cache entry is deleted. Deleted cache entries will be rebuilt when the next matching multicast datagrams are received. 3. Discussion On multi-access networks (either broadcast, NBMA or Point-to- MultiPoint), Prune-LSAs are flooded to more routers than they need to be. They only need be sent to the single upstream router. This document does not specify sufficient functionality to handle to source-specific joins and leaves proposed for IGMPv3, although it is a start. Moy [Page 8] Internet Draft MOSPF Prunes December 1998 4. References [1] Moy, J., "Multicast Extensions to OSPF", , Ascend Communications, Inc., August 1998. [2] Moy, J., "OSPF Version 2", STD 54, RFC 2328, Ascend Communications, Inc., April 1998. [3] Pusateri, T., "Distance Vector Multicast Routing Protocol", , Juniper Networks, August 1998. [4] Moy, J., "Extending OSPF to Support Demand Circuits", RFC 1793, Cascade, April 1995. [5] Coltun, R., "The OSPF Opaque LSA Option", RFC 2370, FORE Systems, July 1998. Moy [Page 9] Internet Draft MOSPF Prunes December 1998 A. The Prune-LSA Prune-LSAs are implemented as link-local Opaque-LSAs (LS type 9), with subtype (Opaque type) equal to 5. A separate Opaque-LSA is originated for each source prefix and destination group combination that the router wishes to prune. The Prune-LSA is then flooded out the interface connecting to the upstream node for the given source prefix and destination group combination. See Section 2 for more information concerning the origination, processing and flushing of Prune-LSAs. 0 1 2 3 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | LS age | Options | 9 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 5 | Prune ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Advertising Router | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | LS sequence number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | LS checksum | length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Source net | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Source mask | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Destination Group | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ The Prune-LSA The Prune-LSA consists of the standard 20-byte link state header (see Section A.4.1 of [OSPF]) followed by the source prefix and destination group specification. Special field definitions within the Prune-LSA are as follows: o Prune ID. A 24-bit integer uniquely identifying each prune currently originated by the router. o Source net, Source mask. Describes the source prefix. o Destination Group. The Class D group address which is pruned for the specified source prefix. Moy [Page 10] Internet Draft MOSPF Prunes December 1998 Security Considerations MOSPF uses the authentication mechanisms supplied by the base OSPF protocol. All OSPF protocol exchanges are authenticated. OSPF supports multiple types of authentication; the type of authentication in use can be configured on a per network segment basis. One of OSPF's authentication types, namely the Cryptographic authentication option, is believed to be secure against passive attacks and provide significant protection against active attacks. For more information, see [OSPF]. Author's Address John Moy Ascend Communications, Inc. 1 Robbins Road Westford, MA 01886 Phone: 978-952-1367 Fax: 978-392-2075 Email: jmoy@casc.com This document expires in May 1999. Moy [Page 11]