RFC relevance of datagram

As per Relevance of the word datagram, we have this rfc below:

Network Working Group J.
Request for Comments: 1584 Proteon, Inc
Category: Standards Track March 1994

Multicast Extensions to

Status of this

This document specifies an Internet standards track protocol for
Internet community, and requests discussion and suggestions
improvements. Please refer to the current edition of the "
Official Protocol Standards" (STD 1) for the standardization
and status of this protocol. Distribution of this memo
unlimited

This memo documents enhancements to the OSPF protocol enabling
routing of IP multicast datagrams. In this proposal, an IP
packet is routed based both on the packet's source and its
destination (commonly referred to as source/destination routing).
it is routed, the multicast packet follows a shortest path to
multicast destination. During packet forwarding, any commonality
paths is exploited; when multiple hosts belong to a single
group, a multicast packet will be replicated only when the paths
the separate hosts diverge

OSPF, a link-state routing protocol, provides a database
the Autonomous System's topology. A new OSPF link
advertisement is added describing the location of
destinations. A multicast packet's path is then calculated
building a pruned shortest-path tree rooted at the packet's
source. These trees are built on demand, and the results of
calculation are cached for use by subsequent packets

The multicast extensions are built on top of OSPF Version 2.
extensions have been implemented so that a multicast
capability can be introduced piecemeal into an OSPF Version 2
routing domain. Some of the OSPF Version 2 routers may run
multicast extensions, while others may continue to be restricted
the forwarding of regular IP traffic (unicasts).

Please send comments to mospf@gated.cornell.edu

Moy [Page 1]

RFC 1584 Multicast Extensions to OSPF March 1994

Table of

1 Introduction ........................................... 4
1.1 Terminology ............................................ 5
1.2 Acknowledgments ........................................ 6
2 Multicast routing in MOSPF ............................. 6
2.1 Routing characteristics ................................ 6
2.2 Sample path of a multicast datagram .................... 8
2.3 MOSPF forwarding mechanism ............................ 10
2.3.1 IGMP interface: the local group database .............. 10
2.3.2 A datagram's shortest-path tree ....................... 14
2.3.3 Support for Non-broadcast networks .................... 16
2.3.4 Details concerning forwarding cache entries ........... 16
3 Inter-area multicasting ............................... 18
3.1 Extent of group-membership-LSAs ....................... 19
3.2 Building inter-area datagram shortest-path trees ...... 22
4 Inter-AS multicasting ................................. 27
4.1 Building inter-AS datagram shortest-path trees ........ 28
4.2 Stub area behavior .................................... 30
4.3 Inter-AS multicasting in a core Autonomous System ..... 31
5 Modelling internal group membership ................... 31
6 Additional capabilities ............................... 33
6.1 Mixing with non-multicast routers ..................... 34
6.2 TOS-based multicast ................................... 35
6.3 Assigning multiple IP networks to a physical network .. 36
6.4 Networks on Autonomous System boundaries .............. 37
6.5 Recommended system configuration ...................... 38
7 Basic implementation requirements ..................... 40
8 Protocol data structures .............................. 40
8.1 Additions to the OSPF area structure .................. 41
8.2 Additions to the OSPF interface structure ............. 42
8.3 Additions to the OSPF neighbor structure .............. 43
8.4 The local group database .............................. 43
8.5 The forwarding cache .................................. 44
9 Interaction with the IGMP protocol .................... 45
9.1 Sending IGMP Host Membership Queries .................. 46
9.2 Receiving IGMP Host Membership Reports ................ 46
9.3 Aging local group database entries .................... 47
9.4 Receiving IGMP Host Membership Queries ................ 47
10 Group-membership-LSAs ................................. 48
10.1 Constructing group-membership-LSAs .................... 49
10.2 Flooding group-membership-LSAs ........................ 52
11 Detailed description of multicast datagram forwarding . 52
11.1 Associating a MOSPF interface with a received datagram 55
11.2 Locating the source network ........................... 55
11.3 Forwarding locally originated multicasts .............. 57
12 Construction of forwarding cache entries .............. 58
12.1 The Vertex data structure ............................. 59

Moy [Page 2]

RFC 1584 Multicast Extensions to OSPF March 1994

12.2 The SPF calculation ................................... 60
12.2.1 Candidate list Initialization: Case SourceIntraArea ... 65
12.2.2 Candidate list Initialization: Case SourceInterArea1 .. 66
12.2.3 Candidate list Initialization: Case SourceInterArea2 .. 66
12.2.4 Candidate list Initialization: Case SourceExternal .... 67
12.2.5 Candidate list Initialization: Case SourceStubExternal 70
12.2.6 Processing labelled vertices .......................... 70
12.2.7 Merging datagram shortest-path trees .................. 71
12.2.8 TOS considerations .................................... 72
12.2.9 Comparison to the unicast SPF calculation ............. 74
12.3 Adding local database entries to the forwarding cache 75
13 Maintaining the forwarding cache ...................... 76
14 Other additions to the OSPF specification ............. 77
14.1 The Designated Router ................................. 77
14.2 Sending Hello packets ................................. 78
14.3 The Neighbor state machine ............................ 78
14.4 Receiving Database Description packets ................ 78
14.5 Sending Database Description packets .................. 79
14.6 Originating Router-LSAs ............................... 79
14.7 Originating Network-LSAs .............................. 79
14.8 Originating Summary-link-LSAs ......................... 80
14.9 Originating AS external-link-LSAs ..................... 80
14.10 Next step in the flooding procedure ................... 81
14.11 Virtual links ......................................... 81
15 References ............................................ 83
Footnotes ............................................. 84
A Data Formats .......................................... 88
A.1 The Options field ..................................... 89
A.2 Router-LSA ............................................ 91
A.3 Group-membership-LSA .................................. 93
B Configurable Constants ................................ 95
B.1 Global parameters ..................................... 95
B.2 Router interface parameters ........................... 95
C Sample datagram shortest-path trees ................... 97
C.1 An intra-area tree .................................... 98
C.2 The effect of areas .................................. 100
C.3 The effect of virtual links .......................... 101
Security Considerations .............................. 102
Author's Address ..................................... 102

Moy [Page 3]

RFC 1584 Multicast Extensions to OSPF March 1994

1.

This memo documents enhancements to OSPF Version 2 to support
multicast routing. The enhancements have been added in a backward
compatible fashion; routers running the multicast additions
interoperate with non-multicast OSPF routers when forwarding
(unicast) IP data traffic. The protocol resulting from the
of the multicast enhancements to OSPF is herein referred to as
MOSPF protocol

IP multicasting is an extension of LAN multicasting to a TCP/
internet. Multicasting support for TCP/IP hosts has been
in [RFC 1112]. In that document, multicast groups are represented
IP class D addresses. Individual TCP/IP hosts join (and leave
multicast groups through the Internet Group Management
(IGMP, also specified in [RFC 1112]). A host need not be a member
a multicast group in order to send datagrams to the group.
datagrams are to be delivered to each member of the multicast
with the same "best-effort" delivery accorded regular (unicast)
data traffic

MOSPF provides the ability to forward multicast datagrams from
IP network to another (i.e., through internet routers).
forwards a multicast datagram on the basis of both the datagram'
source and destination (this is sometimes called source/
routing). The OSPF link state database provides a
description of the Autonomous System's topology. By adding a
type of link state advertisement, the group-membership-LSA,
location of all multicast group members is pinpointed in
database. The path of a multicast datagram can then be calculated
building a shortest-path tree rooted at the datagram's source.
branches not containing multicast members are pruned from the tree
These pruned shortest-path trees are initially built when the
datagram is received (i.e., on demand). The results of the
path calculation are then cached for use by subsequent
having the same source and destination

OSPF allows an Autonomous System to be split into areas. However
when this is done complete knowledge of the Autonomous System'
topology is lost. When forwarding multicasts between areas,
incomplete shortest-path trees can be built. This may lead to
inefficiency in routing. An analogous situation exists when
source of the multicast datagram lies in another Autonomous System
In both cases (i.e., the source of the datagram belongs to
different OSPF area, or to a different Autonomous system)
neighborhood immediately surrounding the source is unknown. In
cases the source's neighborhood is approximated by OSPF summary
advertisements or by OSPF AS external link

Moy [Page 4]

RFC 1584 Multicast Extensions to OSPF March 1994

respectively

Routers running MOSPF can be intermixed with non-multicast
routers. Both types of routers can interoperate when
regular (unicast) IP data traffic. Obviously, the forwarding
of IP multicasts is limited by the number of MOSPF routers
in the Autonomous System (and their interconnection, if any).
ability to "tunnel" multicast datagrams through non-
routers is not provided. In MOSPF, just as in the base
protocol, datagrams (multicast or unicast) are routed "as is" --
they are not further encapsulated or decapsulated as they
the Autonomous System

1.1.

This memo uses the terminology listed in section 1.2 of [OSPF].
For this reason, terms such as "Network", "Autonomous System
and "link state advertisement" are assumed to be understood.
addition, the abbreviation LSA is used for "link
advertisement". For example, router links advertisements
referred to as router-LSAs and the new link state
describing the location of members of a multicast group
referred to as a group-membership-LSA

[RFC 1112] discusses the data-link encapsulation of IP
datagrams. In contrast to the normal forwarding of IP
datagrams, on a broadcast network the mapping of an IP
destination to a data-link destination address is not done
the ARP protocol. Instead, static mappings have been
from IP multicast destinations to data-link addresses.
mappings are dependent on network type; for some networks
multicasts are algorithmically mapped to data-link
addresses, for other networks all IP multicast destinations
mapped onto the data-link broadcast address. This
loosely describes both of these possible mappings as data-
multicast

The following terms are also used throughout this document

o Non-multicast router. A router running OSPF Version 2,
not the multicast extensions. These routers do not
multicast datagrams, but can interoperate with MOSPF
in the forwarding of unicast packets. Routers running
MOSPF protocol are referred to herein as either multicast
capable routers or MOSPF routers

o Non-broadcast networks. A network supporting the
of more than two stations, but not supporting the

Moy [Page 5]

RFC 1584 Multicast Extensions to OSPF March 1994

of a single physical datagram to multiple
(i.e., not supporting data-link multicast). [OSPF]
these networks as non-broadcast, multi-access networks.
example of a non-broadcast network is an X.25 PDN

o Transit network. A network having two or more OSPF
attached. These networks can forward data traffic that
neither locally-originated nor locally-destined. In OSPF
with the exception of point-to-point networks and
links, the neighborhood of each transit network is
by a network links advertisement (network-LSA).

o Stub network. A network having only a single OSPF
attached. A network belonging to an OSPF system is either
transit or a stub network, but never both

1.2.

The multicast extensions to OSPF are based on Link-
Multicast Routing algorithm presented in [Deering]. In addition
the [Deering] paper contains a section on Hierarchical
Routing (providing the ideas for MOSPF's inter-area
scheme) and several Distance Vector (also called Bellman-Ford
multicast algorithms. One of these Distance Vector
algorithms, Truncated Reverse Path Broadcasting, has
implemented in the Internet (see [RFC 1075]).

The MOSPF protocol has been developed by the MOSPF Working
of the Internet Engineering Task Force. Portions of this
have been supported by DARPA under NASA contract NAG 2-650.

2. Multicast routing in

This section describes MOSPF's basic multicast routing algorithm
The basic algorithm, run inside a single OSPF area, covers the
where the source of the multicast datagram is inside the
itself. Within the area, the path of the datagram forms a
rooted at the datagram source

2.1. Routing

As a multicast datagram is forwarded along its shortest-
tree, the datagram is delivered to each member of
destination multicast group. In MOSPF, the forwarding of
multicast datagram has the following properties

o The path taken by a multicast datagram depends both on
datagram's source and its multicast destination.

Moy [Page 6]

RFC 1584 Multicast Extensions to OSPF March 1994

source/destination routing, this is in contrast to
unicast datagram forwarding algorithms (like OSPF)
route based solely on destination

o The path taken between the datagram's source and
particular destination group member is the least cost
available. Cost is expressed in terms of the OSPF link-
metric. For example, if the OSPF metric represents delay,
minimum delay path is chosen. OSPF metrics are configurable
A metric is assigned to each outbound router interface
representing the cost of sending a packet on that interface
The cost of a path is the sum of its constituent (outbound
router interfaces[1].

o MOSPF takes advantage of any commonality of least cost
to destination group members. However, when members of
multicast group are spread out over multiple networks,
multicast datagram must at times be replicated.
replication is performed as few times as possible (at
tree branches), taking maximum advantage of common
segments

o For a given multicast datagram, all routers calculate
identical shortest-path tree. There is a single path
the datagram's source and any particular destination
member. This means that, unlike OSPF's treatment of
(unicast) IP data traffic, there is no provision for equal
cost multipath

o On each packet hop, MOSPF normally forwards IP
datagrams as data-link multicasts. There are two exceptions
First, on non-broadcast networks, since there are no data
link multicast/broadcast services the datagram must
forwarded to specific MOSPF neighbors (see Section 2.3.3).
Second, a MOSPF router can be configured to forward
multicasts on specific networks as data-link unicasts,
order to avoid datagram replication in certain
situations (see Section 6.4).

While MOSPF optimizes the path to any given group member,
does not necessarily optimize the use of the internetwork as
whole. To do so, instead of calculating source-based shortest
path trees, something similar to a minimal spanning
(containing only the group members) would need to be calculated
This type of minimal spanning tree is called a Steiner tree
the literature. For a comparison of shortest-path tree
to routing using Steiner trees, see [Deering2] and [Bharath
Kumar].

Moy [Page 7]

RFC 1584 Multicast Extensions to OSPF March 1994

2.2. Sample path of a multicast

As an example of multicast datagram routing in MOSPF,
the sample Autonomous System pictured in Figure 1. This
has been taken from the OSPF specification (see [OSPF]).
larger rectangles represent routers, the smaller
hosts. Oblongs and circles represent multi-access networks[2].
Lines joining routers are point-to-point serial connections.
cost has been assigned to each outbound router interface

All routers in Figure 1 are assumed to be running MOSPF.
number of hosts have been added to the figure. The
labelled Ma have joined a particular multicast group (call
Group A) via the IGMP protocol. These hosts are located
networks N2, N6 and N11. Similarly, using IGMP the
labelled Mb have joined a separate multicast group B;
hosts are located on networks N1, N2 and N3. Note that hosts
join multiple multicast groups; it is only for clarity
presentation that each host has joined at most one
group in this example. Also, hosts H2 through H5 have
added to the figure to serve as sources for multicast datagrams
Again, the datagrams' sources have been made separate from
group members only for clarity of presentation

To illustrate the forwarding of a multicast datagram,
that Host H2 (attached to Network N4) sends a multicast
to multicast group B. This datagram originates as a data-
layer multicast on Network N4. Router RT3, being a
router, has "opened up" its interface data-link
filters. It therefore receives the multicast datagram,
attempts to forward it to the members of multicast group
(located on networks N1, N2 and N3). This is accomplished
sending a single copy of the datagram onto Network N3, again
a data-link multicast[3]. Upon receiving the multicast
from RT3, routers RT1 and RT2 will then multicast the
on their connected stub networks (N1 and N2 respectively).
that, since the datagram is sent onto Network N3 as a data-
multicast, Router RT4 will also receive a copy. However, it
not forward the datagram, since it does not lie on a
path between the source (Host H2) and any members of
group B

Note that the path of the multicast datagram depends on
datagram's source network. If the above multicast datagram
instead originated by Host H3, the path taken would
identical, since hosts H2 and H3 lie on the same
(Network N4). However, if the datagram was originated by
H4, its path would be different. In this case, when Router RT

Moy [Page 8]

RFC 1584 Multicast Extensions to OSPF March 1994

+
| 3+---+ +--+ +--+ N12 N14
N1|--|RT1|\1 |Mb| |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 |
+--+ +--+ \ | / +--+ | |
+---------+ | |
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 + |1
+--+ 10+----+ N8 +---+
|H1|-----|RT12| |RT8|
+--+SLIP +----+ +---+ +--+
|2 |4 _|H5|
| | / +--+
+---------+ +--------+
N10 N

Figure 1: A sample MOSPF

Moy [Page 9]

RFC 1584 Multicast Extensions to OSPF March 1994

receives the datagram, RT3 will drop the datagram instead
forwarding it (since RT3 is no longer on the shortest path
any member of Group B).

Note that the path of the multicast datagram also depends on
destination multicast group. If Host H2 sends a multicast
Group A, the path taken is as follows. The datagram again
as a multicast on Network N4. Router RT3 receives it,
creates two copies. One is sent onto Network N3 which is
forwarded onto Network N2 by RT2. The other copy is sent
Router RT10 (via RT6), where the datagram is again split
eventually to be delivered onto networks N6 and N11. Note that
although multiple copies of the datagram are produced,
datagram itself is not modified (except for its IP TTL) as it
forwarded. No encapsulation of the datagram is performed;
destination of the datagram is always listed as the
group A

2.3. MOSPF forwarding

Each MOSPF router in the path of a multicast datagram bases
forwarding decision on the contents of a data cache. This
is called the forwarding cache. There is a separate
cache entry for each source/destination combination[4].
cache entry indicates, for multicast datagrams having
source and destination, which neighboring node (i.e., router
network) the datagram must be received from (called the
node) and which interfaces the datagram should then be
out of (called the downstream interfaces).

A forwarding cache entry is actually built from two
pieces. The first of these components is called the local
database. This database, built by the IGMP protocol,
the group membership of the router's directly attached networks
The local group database enables the local delivery of
datagrams. The second component is the datagram's shortest
tree. This tree, built on demand, is rooted at a
datagram's source. The datagram's shortest path tree enables
delivery of multicast datagrams to distant (i.e., not
attached) group members

2.3.1. IGMP interface: the local group

The local group database keeps track of the group
of the router's directly attached networks. Each entry
the local group database is a [group, attached network
pair, which indicates that the attached network has one
more IP hosts belonging to the IP multicast

Moy [Page 10]

RFC 1584 Multicast Extensions to OSPF March 1994

group. This information is then used by the router
deciding which directly attached networks to forward
received IP multicast datagram onto, in order to
delivery of the datagram to (local) group members

The local group database is built through the operation
the Internet Group Management Protocol (IGMP; see [
1112]). When a MOSPF router becomes Designated Router on
attached network (call the network N1), it starts
periodic IGMP Host Membership Queries on the network.
then respond with IGMP Host Membership Reports, one for
multicast group to which they belong. Upon receiving a
Membership Report for a multicast group A, the
updates its local group database by adding/refreshing
entry [Group A, N1]. If at a later time Reports for Group
cease to be heard on the network, the entry is then
from the local group database

It is important to note that on any particular network,
sending of IGMP Host Membership Queries and the listening
IGMP Host Membership Reports is performed solely by
Designated Router. A MOSPF router ignores Host
Reports received on those networks where the router has
been elected Designated Router[5]. This means that at
one router performs these IGMP functions on any
network, and ensures that the network appears in the
group database of at most one router. This
multicast datagrams from being replicated as they
delivered to local group members. As a result, each
in the Autonomous System has a different local
database. This is in contrast to the MOSPF link
database, and the datagram shortest-path trees (see
2.3.2), all of which are identical in each router
to the Autonomous System

The existence of local group members must be communicated
the rest of the routers in the Autonomous System.
ensures that a remotely-originated multicast datagram
be forwarded to the router for distribution to its
group members. This communication is accomplished
the creation of a group-membership-LSA. Like other
state advertisements, the group-membership-LSA is
throughout the Autonomous System. The router originates
separate group-membership-LSA for each multicast
having one or more entries in the router's local
database. The router's group-membership-LSA (say for
A) lists those local transit vertices (i.e., the
itself and/or any directly connected transit networks)

Moy [Page 11]

RFC 1584 Multicast Extensions to OSPF March 1994

should not be pruned from Group A's datagram shortest-
trees. The router lists itself in its group-membership-
for Group A if either 1) one or more of the router'
attached stub networks contain Group A members or 2)
router itself is a member of Group A. The router lists
directly connected transit network in the group-membership
LSA for Group A if both 1) the router is Designated
on the network and 2) the network contains one or more
A members

Consider again the example pictured in Figure 1. If
RT3 has been elected Designated Router for Network N3,
Table 1: lists the local group database for the
RT1-RT4.

In this case, each of the routers RT1, RT2 and RT3
originate a group-membership-LSA for Group B. In addition
RT2 will also be originating a group-membership-LSA
Group A. RT1 and RT2's group-membership-LSAs will
solely the routers themselves (N1 and N2 are stub networks).
RT3's group-membership-LSA will list the transit Network N3.

Figure 2 displays the Autonomous System's link
database. A router/transit network is labelled with
multicast group if (and only if) it has been mentioned in
group-membership-LSA for the group When building
shortest-path tree for a particular multicast datagram,
labelling enables those branches without group members to
pruned from the tree. The process of building a
datagram's shortest path tree is discussed in Section 2.3.2.

Note that none of the hosts in Figure 1 belonging
multicast groups A and B show up explicitly in the
state database (see Figure 2). In fact, looking at the
state database you cannot even determine which stub

Router local group
_____________________________________
RT1 [Group B, N1]
RT2 [Group A, N2], [Group B, N2]
RT3 [Group B, N3]
RT4

Table 1: Sample local group

Moy [Page 12]

RFC 1584 Multicast Extensions to OSPF March 1994

**FROM**

|RT|RT|RT|RT|RT|RT|RT|RT|RT|RT|RT|RT
|1 |2 |3 |4 |5 |6 |7 |8 |9 |10|11|12|N3|N6|N8|N9|
----- ---------------------------------------------
RT1| | | | | | | | | | | | |0 | | | |
RT2| | | | | | | | | | | | |0 | | | |
RT3| | | | | |6 | | | | | | |0 | | | |
RT4| | | | |8 | | | | | | | |0 | | | |
RT5| | | |8 | |6 |6 | | | | | | | | | |
RT6| | |8 | |7 | | | | |5 | | | | | | |
RT7| | | | |6 | | | | | | | | |0 | | |
* RT8| | | | | | | | | | | | | |0 | | |
* RT9| | | | | | | | | | | | | | | |0 |
T RT10| | | | | |7 | | | | | | | |0 |0 | |
O RT11| | | | | | | | | | | | | | |0 |0 |
* RT12| | | | | | | | | | | | | | | |0 |
* N1|3 | | | | | | | | | | | | | | | |
N2| |3 | | | | | | | | | | | | | | |
N3|1 |1 |1 |1 | | | | | | | | | | | | |
N4| | |2 | | | | | | | | | | | | | |
N6| | | | | | |1 |1 | |1 | | | | | | |
N7| | | | | | | |4 | | | | | | | | |
N8| | | | | | | | | |3 |2 | | | | | |
N9| | | | | | | | |1 | |1 |1 | | | | |
N10| | | | | | | | | | | |2 | | | | |
N11| | | | | | | | |3 | | | | | | | |
N12| | | | |8 | |2 | | | | | | | | | |
N13| | | | |8 | | | | | | | | | | | |
N14| | | | |8 | | | | | | | | | | | |
N15| | | | | | |9 | | | | | | | | | |
H1| | | | | | | | | | | |10| | | | |

Figure 2: The MOSPF database

Networks and routers are represented by vertices
An edge of cost X connects Vertex A to Vertex B
the intersection of Column A and Row B is
with an X. In addition, RT1, RT2 and N3 are
with multicast group A and RT1, N6 and RT9
labelled with multicast group B

Moy [Page 13]

RFC 1584 Multicast Extensions to OSPF March 1994

contain multicast group members. The link state
simply indicates those routers/transit networks
attached group members. This is all that is necessary
successful forwarding of multicast datagrams

2.3.2. A datagram's shortest-path

While the local group database facilitates the
delivery of multicast datagrams, the datagram's shortest
path tree describes the intermediate hops taken by
multicast datagram as it travels from its source to
individual multicast group members. As mentioned above,
datagram's shortest-path tree is a pruned shortest-path
rooted at the datagram's source. Two datagrams
differing [source net, multicast destination] pairs
have, and in fact probably will have, different
shortest-path trees

A datagram's shortest path tree is built "on demand"[6],
i.e., when the first multicast datagram is received having
particular [source net, multicast destination] combination
To build the datagram's shortest-path tree, the
calculations are performed. First, the datagram's source
network is located in the link state database. Then
the router-LSAs and network-LSAs in the link state database
a shortest-path tree is built having the source network
root. To complete the process, the branches that do
contain routers/transit networks that have been
with the particular multicast destination (via a group
membership-LSA) are pruned from the tree

As an example of the building of a datagram's shortest
tree, again consider the Autonomous System in Figure 1.
Autonomous System's link state database is pictured
Figure 2. When a router initially receives a
datagram sent by Host H2 to the multicast group A,
following steps are taken: Host H2 is first determined to
on Network N4. Then the shortest path tree rooted at net N
is calculated[7], pruning those branches that do not
routers/transit networks that have been labelled with
multicast group A. This results in the pruned shortest-
tree pictured in Figure 3. Note that at this point all
leaves of the tree are routers/transit networks
with multicast group A (routers RT2 and RT9 and
Network N6).

In order to forward the multicast datagram, each router
find its own position in the datagram's shortest path tree

Moy [Page 14]

RFC 1584 Multicast Extensions to OSPF March 1994

o RT3 (N4, origin
/ \
1/ \8
/ \
N3 (Mb) o o RT
/ \
0/ \7
/ \
RT2 (Ma,Mb) o o RT10
/ \
3/ \1
/ \
N8 o o N6 (Ma
/
0/
/
RT11
/
1/
/
N9
/
0/
/
RT9 (Ma)

Figure 3: Sample datagram's shortest-path tree
source N4, destination Group

The router's (call it Router RTX) position in the datagram'
pruned shortest-path tree consists of 1) RTX's parent in
tree (this will be the forwarding cache entry's
node) and 2) the list of RTX's interfaces that lead
downstream routers/transit networks that have been
with the datagram's destination (these will be added to
forwarding cache entry as downstream interfaces). Note
after calculating the datagram's shortest path tree,
router may find that it is itself not on the tree.
would be indicated by a forwarding cache entry having
upstream node or an empty list of downstream interfaces

As an example of a router describing its position on
datagram's shortest-path tree, consider Router RT10
Figure 3. Router RT10's upstream node for the datagram
Router RT6, and there are two downstream interfaces:

Moy [Page 15]

RFC 1584 Multicast Extensions to OSPF March 1994

connecting to Network N6 and the other connecting to
N8.

2.3.3. Support for Non-broadcast

When forwarding multicast datagrams over non-
networks, the datagram cannot be sent as a link-
multicast (since neither link-level multicast nor
are supported on these networks), but must instead
forwarded separately to specific neighbors. To
this, forwarding cache entries can also contain
neighbors as well as downstream interfaces

The IGMP protocol is not defined over non-
networks. For this reason, there cannot be group
directly attached to non-broadcast networks, nor do non
broadcast networks ever appear in local group
entries

As an example, suppose that Network N3 in Figure 1 is
X.25 PDN. Consider Router RT3's forwarding cache entry
datagrams having source Network N4 and multicast
Group B. In place of having the interface to Network N
appear as the downstream interface in the
forwarding cache entry, the neighboring routers RT1 and RT
would instead appear as separate downstream neighbors.
addition, in this case there could not be a Group B
directly attached to Network N3.

2.3.4. Details concerning forwarding cache

Each of the downstream interface/neighbors in the
entry is labelled with a TTL value. This value indicates
number of hops a datagram forwarded out of the interface (
forwarded to the neighbor) would have to travel
encountering a router/transit network requesting
multicast destination. The reason that a hop count
associated with each downstream interface/neighbor is
that IP multicast's expanding ring search procedure can
more efficiently implemented. By expanding ring search
meant the following. Hosts can restrict the
extent of the IP multicast datagrams that they send
appropriate setting of the TTL value in the datagram's
header. Then, for example, to search for the nearest
the host can send multicasts first with TTL set to 1,
2, etc. By attaching a hop count to each
interface/neighbor in the forwarding cache, datagrams
not be forwarded unless they will ultimately reach

Moy [Page 16]

RFC 1584 Multicast Extensions to OSPF March 1994

multicast destination before their TTL expires[8].
avoids wasting network bandwidth during an expanding
search

As an example consider Router RT10's forwarding cache
Figure 3. Router RT10's cache entry has two
interfaces. The first, connecting to Network N6, is
as having a group member one hop away (Network N6).
second, which connects to Network N8, is labelled as
a group member two hops away (Router RT9).

Both the datagram shortest path tree and the local
database may contribute downstream interfaces to
forwarding cache entries. As an example, if a router has
local group database entry of [Group G, NX], then
forwarding cache entry for Group G, regardless
destination, will list the router interface to Network NX
a downstream interface. Such a downstream interface
always be labelled with a TTL of 1.

As an example of forwarding cache entries, again
the Autonomous System pictured in Figure 1. Suppose Host H
sends a multicast datagram to multicast group A. In
case, some routers will not even attempt to build
forwarding cache entry (e.g, router RT5) because they
never receive the multicast datagram in the first place
Other routers will receive the multicast datagram (
they are forwarded as link-level multicasts), but
building the pruned shortest path tree will notice that
themselves are not a part of the tree (routers RT1, RT4,
RT7, RT8 and RT12). These latter routers will install
empty cache entry, indicating that they do not
in the forwarding of the multicast datagram. A sample of
forwarding cache entries built by the other routers in
Autonomous System is pictured in Table 2.

A MOSPF router must clear its entire forwarding cache
the Autonomous System's topology changes, because all
datagram shortest-path trees must be rebuilt. Likewise,
the location of a multicast group's membership
(reflected by a change in group-membership-LSAs), all
entries associated with the particular multicast
group must be cleared. Other than these two cases
forwarding cache entries need not ever be deleted
otherwise modified; in particular, the forwarding
entries do not have to be aged. However, forwarding
entries can be freely deleted after some period
inactivity (i.e., garbage collected), if router

Moy [Page 17]

RFC 1584 Multicast Extensions to OSPF March 1994

Router Upstream Downstream
node (interface:hops
___________________________________________
RT10 Router RT6 (N6:1), (N8:2)
RT11 Net N8 (N9:1)
RT3 Net N4 (N3:1), (RT6:3)
RT6 Router RT3 (RT10:2)
RT2 Net N3 (N2:1)

Table 2: Sample forwarding cache entries
for source N4 and destination Group A

resources are in short supply

3. Inter-area

Up to this point this memo has discussed multicast forwarding
the entire Autonomous System is a single OSPF area. The logic
when the multicast datagram's source and its destination
members belong to the same OSPF area is the same. This
explains the behavior of the MOSPF protocol when the datagram'
source and (at least some of) its destination group members
to different OSPF areas. This situation is called inter-
multicast

Inter-area multicast brings up the following issues, which
resolved in succeeding sections

o Are the group-membership-LSAs specific to a single area? And
they are, how is group membership information conveyed from
area to the next

o How are the datagram shortest-path trees built in the inter-
case, since complete information concerning the topology of
datagram source's neighborhood is not available to routers
other areas

o In an area border router, multiple datagram shortest-path
are built, one for each attached area. How are these
datagram shortest-path trees combined into a single
cache entry

It should be noted in the following that the basic
mechanisms in the inter-area case are the same as for the intra-
case. Forwarding of multicasts is still defined by the contents

Moy [Page 18]

RFC 1584 Multicast Extensions to OSPF March 1994

the forwarding cache. The forwarding cache is still built from
same two components: the local group database and the
shortest-path trees. And while the calculation of the
shortest-path trees is different in the inter-area case (see
3.2), the local group database is built exactly the same as in
intra-area case (i.e., MOSPF's interface with IGMP remains
in the presence of areas). Finally, the forwarding
described in Section 11 is the same for both the intra-area
inter-area cases

The following discussion uses the area configuration pictured
Figure 4 as an example. This figure, taken from the
specification, shows an Autonomous System split into three
(Area 1, Area 2 and Area 3). A single backbone area has
configured (everything outside of the shading). Since the
area must be contiguous, a single virtual link has been
between the area border routers RT10 and RT11. Additionally, an
address range has been configured in Router RT11 so that
N9-N11 and Host H1 will be reported as a single route outside
Area 3 (via summary-link-LSAs).

3.1. Extent of group-membership-

Group-membership-LSAs are specific to a single OSPF area.
means that, just as with OSPF router-LSAs, network-LSAs
summary-link-LSAs, a group-membership-LSA is flooded
a single area only[9]. A router attached to multiple
(i.e., an area border router) may end up originating
group-membership-LSAs concerning a single multicast destination
one for each attached area. However, as we will see below,
contents of these group-membership-LSAs will vary depending
their associated areas

Just as in OSPF, each MOSPF area has its own link
database. The MOSPF database is simply the OSPF link
database enhanced by the group-membership-LSAs. Consider
the area configuration pictured in Figure 4. The result
adding the group-membership-LSAs to the area databases
the databases pictured in Figures 6 and 7. Figure 6 shows
1's MOSPF database. Figure 7 shows the backbone's
database. Superscripts indicate which transit vertices have
advertised as requesting particular multicast destinations.
superscript of "w" indicates that the router is
itself as a wild-card multicast receiver (see below). The
lines are OSPF summary-link-LSAs or AS external-link-LSAs.
in Figure 7 that Router RT11 has condensed its routes
Networks N9-N11 and Host H1 into a single summary-link-LSA

Moy [Page 19]

RFC 1584 Multicast Extensions to OSPF March 1994

..................................
. + .
. | 3+---+ +--+ +--+ . N12 N14
. N1|--|RT1|\1 |Mb| |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 4: A sample MOSPF area

Moy [Page 20]

RFC 1584 Multicast Extensions to OSPF March 1994

Suppose an OSPF router has a local group database entry
[Group Y, Network X]. The router then originates a group
membership-LSA for Group Y into the area containing Network X
For example, in the area configuration pictured in Figure 4,
Router RT1 originates a group-membership-LSA for Group B.
group-membership-LSA is flooded throughout Area 1, and
further. Likewise, assuming that Router RT3 has been
Designated Router for Network N3, RT3 originates a group
membership-LSA into Area 1 listing the transit Network N3
having group members. Note that in the link state database
Area 1 (Figure 6) both Router RT1 and Network N3
accordingly been labelled with Group B

In OSPF, the area border routers forward routing information
data traffic between areas. In MOSPF. a subset of the
border routers, called the inter-area multicast forwarders
forward group membership information and multicast
between areas. Whether a given OSPF area border router is also
MOSPF inter-area multicast forwarder is configuration
(see Section B.1). In Figure 4 we assume that all area
routers are also inter-area multicast forwarders

In order to convey group membership information between areas
inter-area multicast forwarders "summarize" their
areas' group membership to the backbone. This is very
functionality to the summary-link-LSAs that are generated in
base OSPF protocol. An inter-area multicast
calculates which groups have members in its attached non
backbone areas. Then, for each of these groups, the inter-
multicast forwarder injects a group-membership-LSA into
backbone area. For example, in Figure 4 there are two
having members in Area 1: Group A and Group B. For that reason
both of Area 1's inter-area multicast forwarders (Routers RT
and RT4) inject group-membership-LSAs for these two groups
the backbone. As a result both of these routers are

membership +------------------+
+ > > > >>| Backbone |< < < < +
^ +------------------+ ^
^ / | \ ^
^ / | \ ^
+----^-----+/ +----------+ \+----^-----+
| Area 1 | | Area 2 | | Area 3 |
+----------+ +----------+ +----------+

Figure 5: Inter-area routing

Moy [Page 21]

RFC 1584 Multicast Extensions to OSPF March 1994

with Groups A and B in the backbone link state database (
Figure 7).

However, unlike the summarization of unicast destinations in
base OSPF protocol, the summarization of group membership
MOSPF is asymmetric. While a non-backbone area's
membership is summarized to the backbone, this information
not then readvertised into other non-backbone areas. Nor is
backbone's group membership summarized for the non-
areas. Going back to the example in Figure 4, while the
of Area 3's group (Group A) is advertised to the backbone,
information is not then redistributed to Area 1. In other words
routers internal to Area 1 have no idea of Area 3's
membership

At this point, if no extra functionality was added to MOSPF
multicast traffic originating in Area 1 destined for
Group A would never be forwarded to those Group A members
Area 3. To accomplish this, the notion of wild-card
receivers is introduced. A wild-card multicast receiver is
router to which all multicast traffic, regardless of
destination, should be forwarded. A router's wild-card
reception status is per-area. In non-backbone areas, all inter
area multicast forwarders[10] are wild-card multicast receivers
This ensures that all multicast traffic originating in a non
backbone area will be forwarded to its inter-area
forwarders, and hence to the backbone area. Since the
has complete knowledge of all areas' group membership,
datagram can then be forwarded to all group members. Note
in the backbone itself there is no need for wild-card
receivers[11]. As an example, note that Routers RT3 and RT4
wild-card multicast receivers in Area 1 (see Figure 6),
there are none in the backbone (see Figure 7).

This yields the inter-area routing architecture pictured
Figure 5. All group membership is advertised by the non
backbone areas into the backbone. Likewise, all IP
traffic arising in the non-backbone areas is forwarded to
backbone. Since at this point group membership information
the multicast datagram traffic, delivery of the
datagrams becomes possible

3.2. Building inter-area datagram shortest-path

When building datagram shortest-path trees in the presence
areas, it is often the case that the source of the datagram
(at least some of) the destination group members are in
areas. Since detailed topological information concerning

Moy [Page 22]

RFC 1584 Multicast Extensions to OSPF March 1994

**FROM**

|RT|RT|RT|RT|RT|RT
|1 |2 |3 |4 |5 |7 |N3|
----- -------------------
RT1| | | | | | |0 |
RT2| | | | | | |0 |
RT3| | | | | | |0 |
* RT4| | | | | | |0 |
* RT5| | |14|8 | | | |
T RT7| | |20|14| | | |
O N1|3 | | | | | | |
* N2| |3 | | | | | |
* N3|1 |1 |1 |1 | | | |
N4| | |2 | | | | |
Ia,Ib| | |15|22| | | |
N6| | |16|15| | | |
N7| | |20|19| | | |
N8| | |18|18| | | |
N9-N11,H1| | |19|16| | | |
N12| | | | |8 |2 | |
N13| | | | |8 | | |
N14| | | | |8 | | |
N15| | | | | |9 | |

Figure 6: Area 1's MOSPF database

Networks and routers are represented by vertices
An edge of cost X connects Vertex A to Vertex B
the intersection of Column A and Row B is
with an X. In addition, RT1, RT2 and N3 are
with multicast group A, RT1 is labelled with
group B, and both RT3 and RT4 are labelled
wild-card multicast receivers

Moy [Page 23]

RFC 1584 Multicast Extensions to OSPF March 1994

**FROM**

|RT|RT|RT|RT|RT|RT|
|3 |4 |5 |6 |7 |10|11|
------------------------
RT3| | | |6 | | | |
RT4| | |8 | | | | |
RT5| |8 | |6 |6 | | |
RT6|8 | |7 | | |5 | |
RT7| | |6 | | | | |
* RT10| | | |7 | | |2 |
* RT11| | | | | |3 | |
T N1|4 |4 | | | | | |
O N2|4 |4 | | | | | |
* N3|1 |1 | | | | | |
* N4|2 |3 | | | | | |
Ia| | | | | |5 | |
Ib| | | |7 | | | |
N6| | | | |1 |1 |3 |
N7| | | | |5 |5 |7 |
N8| | | | |4 |3 |2 |
N9-N11,H1| | | | | | |1 |
N12| | |8 | |2 | | |
N13| | |8 | | | | |
N14| | |8 | | | | |
N15| | | | |9 | | |

Figure 7: The backbone's MOSPF database

Networks and routers are represented by vertices
An edge of cost X connects Vertex A to Vertex B
the intersection of Column A and Row B is
with an X. In addition, RT3 and RT4 are
with both multicast groups A and B, and RT7, RT10,
and RT11 are labelled with multicast group A

OSPF area is not distributed to other OSPF areas (the
of router-LSAs, network-LSAs and group-membership-LSAs
restricted to a single OSPF area only), the building of
datagram shortest-path trees is often impossible in the inter
area case. To compensate, approximations are made through
use of wild-card multicast receivers and OSPF summary-link-LSAs

When it first receives a datagram for a particular [source net
destination group] pair, a router calculates a separate
shortest-path tree for each of the router's attached areas.
datagram shortest-path tree is built solely from LSAs

Moy [Page 24]

RFC 1584 Multicast Extensions to OSPF March 1994

to the particular area's link state database. Suppose that
router is calculating a datagram shortest-path tree for Area A
It is useful then to separate out two cases

The first case, Case 1: The source of the datagram belongs
Area A has already been described in Section 2.3.2. However,
the presence of OSPF areas, during tree pruning care must
taken so that the branches leading to other areas remain,
it is unknown whether there are group members in these (remote
areas. For this reason, only those branches having no
members nor wild-card multicast receivers are pruned
producing the datagram shortest-path tree

As an example, suppose in Figure 4 that Host H2 sends
multicast datagram to destination Group A. Then the datagram'
shortest-path tree for Area 1, built identically by all
in Area 1 that receive the datagram, is shown in Figure 8.
that both inter-area multicast forwarders (RT3 and RT4) are
the datagram's shortest-path tree, ensuring the delivery of
datagram to