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", <draft-ietf-mospf-
mospf-00.txt>, 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",
<draft-ietf-idmr-dvmrp-v3-07.txt>, 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]
