RFC 1584
Multicast Extensions to OSPF
Pages: 102
Historic
Historic
Part 3 of 4 – Pages 52 to 76
11. Detailed description of multicast datagram forwarding This section describes in detail the way MOSPF forwards a multicast datagram. The forwarding process has already been informally presented in Section 2.2. However, there are several obscure configuration options (e.g., the IPMulticastForwarding interface parameter) that have been presented elsewhere in this document, which may influence the forwarding process. This section gathers together all the influencing factors into a single algorithm. It is assumed in the following that the datagram under consideration has actually be received on one of the router's interfaces. Locally generated datagrams (i.e., originated by one of the router's internal applications) are handled instead by the algorithm in Section 11.3.
Assume that the datagram's IP destination is Group G. The forwarding
process then consists of the following steps:
(1) Upon reception of the datagram, the MOSPF router notes the
following parameters. These parameters are examined in later
steps, to determine whether the datagram should be forwarded.
a. The receiving MOSPF interface associated with the datagram.
Based on the receiving physical interface, the receiving
MOSPF interface is selected by the algorithm in Section
11.1.
b. Whether the datagram was received as a link-level
multicast/broadcast or as a link-level unicast. This
information is used later in Step 7 to help determine
whether the datagram should be forwarded.
(2) A copy of the datagram should be passed to each internal
application that has joined Group G on the receiving MOSPF
interface (see Section 5).
(3) If the datagram's IP source address matches the receiving MOSPF
interface's IP address, the datagram should not be forwarded
further, and should instead be discarded, completing the
forwarding process. This keeps the router's own locally
originated datagrams from being mistakenly replicated, in those
cases where the receiving MOSPF interface receives its own
multicast transmissions.
(4) If Group G falls into the range 224.0.0.1 through 224.0.0.255
inclusive, the datagram should not be forwarded further. This
range of addresses has been dedicated for use on a local network
segment only.
(5) Associate a source network (SourceNet) with the multicast
datagram, as described in Section 11.2. If SourceNet cannot be
determined (i.e., there is no available unicast route back to
the datagram source), the datagram should not be forwarded
further.
(6) Look up the forwarding cache entry (see Section 8.5) matching
the datagram's [SourceNet, Group G, TOS] combination. If the
cache entry does not yet exist, one is built by the calculation
in Section 12. In order for the datagram to be forwarded, the
contents of the forwarding cache entry must be further verified
against the received datagram's characteristics as follows:
a. If the forwarding cache entry's upstream node is unspecified
(i.e., NULL), then the datagram should not be forwarded
further.
b. Otherwise, suppose that the forwarding cache entry's
upstream node is set to EXTERNAL. In this case, the datagram
is forwarded further if and only if the receiving MOSPF
interface is set to NULL (i.e., if and only if the datagram
was received on a non-MOSPF interface).
c. Otherwise, if the datagram's receiving MOSPF interface does
not attach to the forwarding cache entry's upstream node,
the datagram should not be forwarded further.
(7) If the receiving MOSPF interface's IPMulticastForwarding
parameter is set to data-link unicast, the datagram should be
forwarded further only if it was received as a data-link
unicast.
(8) At this point the datagram is eligible for further forwarding.
Before forwarding, the router checks to see whether it has any
internal applications that have joined Group G on an interface-
independent basis. If so, a copy of the datagram should be
passed to each such requesting application process.
(9) Examine each of the downstream interfaces listed in the
forwarding cache entry. If the TTL in the datagram is greater
than or equal to the TTL specified for the downstream interface,
a copy of the datagram should be forwarded out the downstream
interface. Before forwarding the datagram copy, the copy's TTL
should be decremented by 1. On most interfaces, the datagram is
forwarded as a data-link multicast/broadcast. The exact data-
link encapsulation is dependent on the attached network's type:
o On ethernet and IEEE 802.3 networks, the datagram is
forwarded as a data-link multicast. The destination data-
link multicast address is selected as an algorithmic
translation of the IP multicast destination. See [RFC 1112]
for details.
o On FDDI networks, the datagram is forwarded as a data-link
multicast. The destination data-link multicast address is
selected as an algorithmic translation of the IP multicast
destination. See [RFC 1390] for details.
o On SMDS networks, the datagram is forwarded using the same
SMDS address that is used by IP broadcast datagrams. See
[RFC 1209] for details.
o On networks that support broadcast, but not multicast (e.g.,
the Experimental Ethernet), the datagram is forwarded as a
data-link broadcast. See [RFC 1112] for details.
o On point-to-point networks, the datagram is forwarded in the
same way that unicast datagrams are forwarded. See [RFC
1112] for details.
(10)
Examine each of the downstream neighbors listed in the
forwarding cache entry. If the TTL in the datagram is greater
than or equal to the TTL specified for the downstream neighbor,
a copy of the datagram should be forwarded to the downstream
neighbor (as a data-link unicast). Before forwarding the
datagram copy, the copy's TTL should be decremented by 1.
ICMP error messages are never generated in response to received IP
multicasts. In particular, ICMP destination unreachables and ICMP
TTL expired messages are not generated by the above procedure if the
router refuses to forward a multicast datagram.
11.1. Associating a MOSPF interface with a received datagram
A MOSPF interface must be associated with a received multicast
datagram before it is forwarded (see Step 1a of Section 11), and
with received IGMP Host Membership Reports before they are
processed (see Section 9.2).
When there is only a single IP network assigned to the physical
interface that received the datagram, the choice of receiving
MOSPF interface is clear. When there are multiple logical IP
networks attached to the receiving physical interface, the
receiving MOSPF interface is selected as follows. Examine all of
the MOSPF interfaces associated with the receiving physical
interface. Discard those interfaces whose IPMulticastForwarding
parameter has been set to disabled. The receiving MOSPF
interface is then the remaining interface having the highest IP
interface address (or NULL if there are no remaining
interfaces)[19].
11.2. Locating the source network
MOSPF forwarding cache entries are indexed by the datagram's
source IP network/subnet/supernet. For this reason, whenever an
IP multicast datagram is received, the IP network belonging to
the datagram's IP source address must be found. This is
accomplished by the following algorithm:
Look up the OSPF TOS 0 routing table entry[20] corresponding to
the datagram's IP source address, as described in Section 11.1
of [OSPF]. If this routing table entry describes an OSPF
intra-area or inter-area route, the source network is set to be
the network defined by the routing table entry's Destination ID
and Address Mask (see Section 11 of [OSPF]). Otherwise (i.e.,
the routing table entry specifies an external route, or there is
no matching routing table entry), the list of matching AS
external-link-LSAs is examined. A matching AS external-link-LSA
is one that describes a network which contains the datagram's IP
source address. The list of matching AS external-link-LSAs is
pruned in the following steps to determine the source network:
(1) Those AS external-link-LSAs with MC-bit clear (see Section
A.1), or with LS age set to MaxAge, or which have been
originated by unreachable AS boundary routers are discarded.
(2) AS external-link-LSAs specifying Type 1 external metrics are
always preferred over those specifying Type 2 external
metrics.
(3) If there are still multiple AS external-link-LSAs remaining,
those specifying the best matching (i.e., most specific)
network are selected. The source network is then set to the
network/subnet/supernet (possibly even the default route)
described by the best matching AS external-link-LSAs. Note
that AS external-link-LSAs specifying a cost of LSInfinity
are eligible for this best match, as long as their MC-bit is
set.[21]
It is possible that two different MOSPF routers may calculate
the same multicast datagram's source network differently. For
example, consider the network configuration shown in Figure 4.
When calculating the source network for a datagram whose source
is Network N10 and destination is Group Ma, Router RT11 would
calculate the source network as Network N10 itself, while Router
RT10 would calculate the source network as the aggregate of
Networks N9-N11 and Host H1 (advertised in a single summary-
link-LSA by Router RT11). However, despite the possibility of
routers selecting different source networks, all routers will
still agree on the datagram's shortest-path tree.
External sources are treated differently in the above
calculation since it is likely that the Internet will have
separate multicast and unicast topologies for some time to come.
When the multicast and unicast topologies do merge, the MC-bit
will be set on all AS external-link-LSAs and the above use of
the LSInfinity metric (to indicate a route that is to be used
for multicast traffic, but not unicast traffic), will no longer
be necessary. At that time, the determination of source network
for external sources will revert to the same simple routing
table lookup that is used for internal sources.
As an example of the logic for external sources, suppose a
multicast datagram is received having the IP source address
10.1.1.1. Suppose also that the three AS external-link-LSAs
shown in Table 3 are in the router's OSPF database. The OSPF
routing table lookup would yield the network 10.1.1.0 with a
mask of 255.255.255.0, however the above calculation would
choose a source network of 10.1.0.0 with a mask of 255.255.0.0,
despite the fact that its matching LSA has a cost of LSInfinity.
11.3. Forwarding locally originated multicasts
This section describes how a MOSPF router forwards a multicast
datagram that has been originated by one of the router's own
internal applications. The process begins with one of the
router's internal applications formatting and addressing the
datagram. Forwarding the locally originated multicast then
consists of the following steps:
(1) Find the router interface whose IP address matches the
datagram's source address. Multicast the datagram out that
interface, according to the Host extensions for IP
multicasting specified in [RFC 1112].
(2) If the router interface found in the previous step has been
configured for MOSPF, and if its IPMulticastForwarding
parameter is not equal to disabled, then set the receiving
MOSPF interface to that interface. Otherwise, set the
receiving MOSPF interface to NULL.
(3) Execute the MOSPF forwarding process described in Section
11, beginning with its Step 4.
Network Mask Cost MC-bit
______________________________________________________
10.1.1.0 255.255.255.0 Type 1: 10 clear
10.1.0.0 255.255.0.0 Type 2: LSInfinity set
10.0.0.0 255.0.0.0 Type 2: 1 set
Table 3: Sample AS external-link-LSAs
The above algorithm amounts to the router always multicasting
the datagram out the source interface, and the executing the
basic forwarding algorithm (in Section 11) as if the datagram
had actually been received on the source interface. In those
cases where the router receives its own multicast transmissions,
unwanted replication is prevented by Step 3 of Section 11. In
fact, this specification has purposely presented the forwarding
algorithm (both for received and for locally originated
datagrams) so that the correct forwarding actions are taken
independent of whether the router receives its own multicast
transmissions.
12. Construction of forwarding cache entries
This section details the building of a MOSPF forwarding cache entry.
A high level discussion of this construction has already been
presented in Sections 2.3, 2.3.1, 2.3.2, 3.2, and 4.1. Forwarding
cache entries are built on demand, when a multicast datagram is
received and no matching forwarding cache entry is found (see Step 6
of Section 11). The parameters passed to the forwarding cache entry
build process are: the datagram's source network (see Section 11.2)
and its destination group address. These two parameters are called
SourceNet and Group G in the following algorithm. The main steps in
the build process are the following:
(1) Allocate the forwarding cache entry. Initialize its Source
network to SourceNet, its Destination multicast group to Group G
and its IP TOS field to match the multicast datagram's TOS.
Initialize its upstream node and list of downstream interfaces
to NULL.
(2) For each Area A to which the calculating router is attached:
a. Calculate Area A's datagram shortest-path tree. This
calculation is described in Section 12.2 below. In many ways
it is similar to the calculation of OSPF's intra-area
routes, described in Section 16.1 of [OSPF]. The main
differences between the multicast datagram shortest-path
tree calculation and OSPF's intra-area unicast calculation
are listed in Section 12.2.9 below. As a product of each
area's datagram shortest-path tree, the forwarding cache
entry's list of outgoing interfaces is (possibly) updated.
Area A's datagram shortest-path tree is dependent on the
datagram's IP TOS. Section 12.2 describes the TOS 0 datagram
shortest-path tree. The modifications necessary for non-zero
TOS values are detailed in Section 12.2.8.
b. Possibly set the forwarding cache entry's upstream node.
Only one of the calculating router's attached areas will
determine the forwarding cache entry's upstream node. This
area is called the datagram's RootArea. The RootArea is
initially set to NULL. After completing Area A's datagram
shortest-path tree, the calculation in Section 12.2.7 will
determine whether Area A is the datagram's RootArea.
(3) Update the forwarding cache entry's list of outgoing interfaces,
according to the contents of the local group database. This
ensures multicast delivery to group members residing on the
calculating router's directly attached networks. This process is
described in Section 12.3.
These main steps are described in more detail below. The detailed
description begins with an explanation of the major data structure
used by the datagram shortest-path tree calculation: The Vertex data
structure.
12.1. The Vertex data structure
A datagram shortest-path tree is built by the Dijkstra or SPF
algorithm. The algorithm is stated herein using graph-oriented
language: vertices and links. Vertices are the area's routers
and transit networks, and links are the router interfaces and
point-to-point lines that connect them. Each vertex has the
following state information attached to it. Basically, this
information indicates the current best path from the SourceNet
to the vertex, and the position of the vertex relative to the
calculating router. Note that a separate datagram shortest-path
tree is built for each area, and that the vertices described
below are also specific to a single area (called Area A).
o Vertex type. Set to 1 for routers, 2 for transit networks.
Note that this coding matches the coding for vertices listed
in the group-membership-LSA (see Section A.3).
o Vertex ID. A 32-bit identifier for the vertex. For routers,
set to the router's OSPF Router ID. For transit networks,
set the IP address of the network's Designated Router. Note
that this coding matches the coding for vertices listed in
the group-membership-LSA (see Section A.3).
o LSA. The link state advertisement describing the vertex'
immediate neighborhood. Can be discovered by performing a
database lookup in Area A's link state database (see Section
12.2 of [OSPF]), with LS type set to Vertex type and Link
State ID set to Vertex ID.
o Parent. In the current best path from SourceNet to the
vertex, the router/transit network immediately preceding the
vertex. Note that the parent can change as better and better
paths are found, up until the vertex is installed on the
shortest-path tree.
o IncomingLinkType. This parameter is set to the type of link
that led to Vertex's inclusion on the shortest-path tree.
Listed in order of decreasing preference[22], the possible
types are: ILVirtual (virtual links), ILDirect (vertex is
directly attached to SourceNet), ILNormal (either router-
to-router or router-to-network links), ILSummary (OSPF
summary links), ILExternal (OSPF AS external links), or
ILNone (the vertex is not on the shortest-path tree).
o AssociatedInterface/Neighbor. If the current best path from
SourceNet to the vertex goes through the calculating router,
this parameter indicates the calculating router's interface
(or neighbor) which leads to the vertex.
o Cost. The cost, in terms of the OSPF link state metric, of
the current best path from SourceNet to the vertex. Note
that if the cost of the path is a combination of both
external type 2 and internal OSPF metrics, that the vertex'
cost parameter reflects both cost components. Remember that
the type 2 cost component is always more significant than
the type 1 component.
o TTL. If the current best path from SourceNet to vertex goes
through the calculating router, TTL is set to the number of
routers between the calculating router and the vertex. This
includes the calculating router, but does not include the
vertex itself.
12.2. The SPF calculation
This section details the construction of datagram shortest-path
trees. Such a tree describes the path of a multicast datagram
as it traverses an OSPF area. For a given datagram, each router
in an OSPF area builds an identical tree. A router connected to
multiple areas builds a separate datagram shortest-path tree for
each area.
The datagram shortest-path tree is built by the Dijkstra or SPF
algorithm, which is the same algorithm used to discover OSPF's
intra-area unicast routes (see Section 16.1 of [OSPF]). The
algorithm is stated herein and in [OSPF] using graph-oriented
language: vertices and links. Vertices are the area's routers
and transit networks, and links are the router interfaces and
point-to-point lines that connect them. Basically, the algorithm
manipulates two lists of vertices: the candidate list and the
forming shortest-path tree. The candidate list consists of those
vertices to which paths have been discovered, but for which the
optimality of the discovered paths is yet unknown. At each cycle
of the algorithm, the vertex closest to the tree's root, yet
still remaining on the candidate list, is moved from the
candidate list to the shortest-path tree. Then the neighbors of
the just processed vertex are examined for possible addition
to/modification of the candidate list. The algorithm terminates
when the candidate list is empty.
The datagram shortest-path tree for Area A is constructed in the
following steps. The datagram's SourceNet and its destination
group G are inputs to the calculation (see Step 6 of Section
11). The datagram shortest-path tree also depends on the IP Type
of service specified in the datagrams' IP Header. However, a
discussion of TOS is deferred until Section 12.2.8; all
calculations and costs in the current section concern TOS 0
only. Call the router performing the calculation Router RTX. At
each step (and in the subordinate Sections 12.2.1 through
12.2.8) LSAs from Area A's link state database are examined. In
all cases, any LSA having LS age equal to MaxAge is ignored. The
main body of the calculation is in Steps 4 and 5, which are
repeated until the candidate list becomes empty:
(1) Initialize the algorithm's data structures. Clear the
shortest-path tree. Initialize the state of each vertex in
Area A (i.e., the area's routers and transit networks) to:
Parent set to NULL, IncomingLinkType set to ILNone and
AssociatedInterface/Neighbor set to NULL.
(2) Initialize the candidate list. One or more vertices are
initially placed on the candidate list, depending on the
location of SourceNet with respect to Area A and Router RTX.
This breaks down into the following cases (which are named
for later reference):
o Case SourceIntraArea: SourceNet belongs to Area A. In
this case, the candidate list is initialized as in
Section 12.2.1.
o Case SourceInterArea1: SourceNet belongs to an OSPF area
that is not directly attached to Router RTX. In this
case, the candidate list is initialized as in Section
12.2.2.
o Case SourceInterArea2: SourceNet does not belong to Area
A, but it still belongs to an OSPF area that is directly
attached to Router RTX. In this case, the candidate
list is initialized as in Section 12.2.3.
o Case SourceExternal: SourceNet is external to the OSPF
routing domain, and Area A is not an OSPF stub area. In
this case, the candidate list is initialized as in
Section 12.2.4.
o Case SourceStubExternal: SourceNet is external to the
OSPF routing domain, and Area A is an OSPF stub area. In
this case, the candidate list is initialized as in
Section 12.2.5.
Two different routers in Area A may select different
initialization cases above. For example, consider the
network configuration shown in Figure 4. When calculating
the Area 3 datagram shortest-path tree for a datagram whose
source is Network N7 (e.g., from Host H5) and destination is
Group Ma, Router RT11 would initialize the candidate list
using Case SourceInterArea2 while Router RT9 would use Case
SourceInterArea1. Likewise, if Area 3 were configured as an
OSPF stub area and the datagram source was the external
Network N12, Router RT11 would use Case SourceStubExternal
while Router RT9 would use Case SourceInterArea1! However,
despite the possibility of routers selecting different
cases, all routers in an area will still initialize the
candidate list (and in fact, run the rest of the SPF
calculation) identically.
(3) If the candidate list is empty, the algorithm terminates.
(4) Move the closest candidate vertex to the shortest-path tree.
Select the vertex on the candidate list that is closest to
SourceNet (i.e., has the smallest Cost value). If there are
multiple possibilities, select transit networks over
routers. If there are still multiple possibilities
remaining, select the vertex having the highest Vertex ID.
Call the chosen vertex Vertex V. Remove Vertex V from the
candidate list, and install it on the shortest-path tree.
Next, determine whether Vertex V has been labelled with the
Destination multicast Group G. If so, it may cause the
forwarding cache entry's list of outgoing
interfaces/neighbors to be updated. See Section 12.2.6 for
details.
(5) Examine Vertex V's neighbors for possible inclusion in the
candidate list. Consider Vertex V's LSA. Each link in the
LSA describes a connection to a neighboring router/network.
If the link connects to a stub network, examine the next
link in the LSA. Otherwise, the link (Link L) connects to a
neighboring transit node. Call this node Vertex W. Perform
the following steps on Vertex W:
a. If W is already on the shortest-path tree, or if W's LSA
does not contain a link back to vertex V, or if W's LSA
has LS age of MaxAge, or if W is not multicast-capable
(indicated by the MC-bit in the LSA's Options field),
examine the next link in V's LSA.
b. Otherwise determine the cost to associate with the link
from V to W. If SourceNet belongs to Area A (Case
SourceIntraArea in Step 2), use the cost listed for Link
L in V's LSA. Otherwise, use the link's reverse cost:
Examine W's LSA, and find the cost listed for the link
connecting back to V. Actually, when V and W are both
routers, there may be multiple links between them. In
this case, use the smallest cost listed in W's LSA for
any of the links connecting back to V and having the
same Type (as specified in the Router-LSA; must be
either: point-to-point connection or virtual link) as
Link L[23].
c. Calculate the cost from SourceNet to W, when using Link
L. It is the sum of the cost of SourceNet to V (i.e.,
V's Cost parameter) plus the link cost calculated in
Step 5b. Let this sum be Cost C. If W is not yet on the
candidate list, install W on the candidate list,
modifying its parameters as specified below (Step 5d).
Otherwise, W is on the candidate list already. In this
case, if:
o C is less than W's current Cost, update W's
parameters on the candidate list as specified below
(Step 5d).
o C is equal to W's current Cost, then the following
tiebreakers are invoked. The type of Link L is
compared to W's current IncomingLinkType, and
whichever link has the preferred type is chosen (the
preference order of link types is listed in Section
12.1's definition of IncomingLinkType). If the link
types are the same, then a link whose Parent is a
transit network is preferred over one whose Parent
is a router. If the links are still equivalent, the
link whose Parent has the higher Vertex ID is
chosen. Whenever Link L is chosen, W's parameters
are modified as below (Step 5d). Whenever the
previously discovered link is chosen, the next link
in V's LSA is examined instead.
o C is greater than W's current Cost, examine the next
link in V's LSA.
d. At this point, a better candidate path has been found to
Vertex W, using Link L. Modify Vertex W's parameters
accordingly. W's Parent is set to Vertex V. W's
IncomingLinkType is set to ILVirtual if Link L is a
virtual link, otherwise IncomingLinkType is set to
ILNormal. W's Cost parameter is set to C. W's TTL and
AssociatedInterface/Neighbor parameters are set
according to one of the following cases:
o Vertex V is the calculating router itself. In this
case, W's TTL parameter is set to 1. If Link L is a
virtual link, W's AssociatedInterface/Neighbor is
set to NULL. Otherwise, W's
AssociatedInterface/Neighbor is set to the non-
virtual interface connecting the calculating router
to W which has the smallest cost value. Note that,
in the reverse cost (inter-area and inter-AS
multicast) cases, this may not be the interface
corresponding to Link L. However, since W is only
concerned with the node it is receiving the datagram
from (the upstream node; see Section 11), and not
with the particular interface the datagram is
received on, the calculating router is free to pick
the sending interface when there are multiple
connecting links.
o Vertex V is upstream of the calculating router
(i.e., V's AssociatedInterface/Neighbor is equal to
NULL). In this case, Vertex W's TTL parameter is set
to 0, and its AssociatedInterface/Neighbor is set to
NULL.
o V is a transit network, and is directly downstream
from the calculating router (i.e., V's
AssociatedInterface/Neighbor is non-NULL and V's TTL
is set to 1). W is then one of the calculating
router's neighbors. In this case, W's TTL parameter
is also set to 1. If network V has been configured
for data-link unicasting (see Section B.2) or if V
is a non-broadcast network, W's
AssociatedInterface/Neighbor is set to W itself (a
neighbor of the calculating router). Otherwise, W's
AssociatedInterface/Neighbor is set to the
calculating router's interface to Network V.
o Vertex V is downstream from the calculating router
(i.e., V's AssociatedInterface/Neighbor is non-
NULL), and either a) V is a router or b) V's TTL
parameter is greater than 1. In these cases, W's
AssociatedInterface/Neighbor parameter is copied
directly from V. If V is a router, W's TTL
parameter is set to V's TTL parameter incremented by
one. If V is a transit network, W's TTL parameter is
set directly to V's TTL parameter.
(6) If the candidate list is non-empty, go to Step 4. Otherwise,
the algorithm terminates.
After the datagram shortest-path tree for Area A is complete,
the calculating router (RTX) must decide whether Area A, out of
all of RTX's attached areas, determines the forwarding cache
entry's upstream node. This determination is described in
Section 12.2.7.
Examples of the above SPF calculation, with particular emphasis
on the tiebreaking rules, are given in Appendix C.
12.2.1. Candidate list Initialization: Case SourceIntraArea
In this case, SourceNet belongs to Area A. The candidate
list is then initialized as follows. Start with the LSA
listed as Link State Origin in the matching OSPF routing
table entry. If this LSA is not multicast-capable (i.e, its
Options field has the MC-bit clear) the candidate list
should be set to NULL. Otherwise, the vertex identified by
the LSA is installed on the candidate list, setting its
vertex parameters as follows: IncomingLinkType set to
ILDirect, Cost set to 0, Parent to NULL and
AssociatedInterface/Neighbor to NULL.
As a consequence of this initialization, note that if
SourceNet is a stub network, then the datagram shortest-path
tree will not actually be rooted at the datagram source, but
will instead be rooted at the MOSPF router that attaches the
stub network to the rest of the MOSPF system. For example,
consider the network configuration shown in Figure 4. When
calculating the Area 2 datagram shortest-path tree for a
datagram whose source is Network N7 (e.g., from Host H5) and
destination is Group Ma, Router RT11 (and all other routers
attached to Area 2) will begin with the candidate list set
to Router RT8. As another example, the datagram shortest-
path tree pictured in Figure 3 is really rooted at Router
RT3 instead of Network N4.
12.2.2. Candidate list Initialization: Case SourceInterArea1
In this case, SourceNet belongs to an OSPF area that is not
directly attached to the calculating router (RTX). The
candidate list is then initialized as follows. Examine the
Area A summary-link-LSAs advertising SourceNet. For each
such summary-link-LSA: if both a) the MC-bit is set in the
LSA's Options field and b) the advertised cost is not equal
to LSInfinity, then the vertex representing the LSA's
advertising area border router is added to the candidate
list. An added vertex' state is initialized as:
IncomingLinkType set to ILSummary, Cost to whatever is
advertised in the LSA, Parent to NULL and
AssociatedInterface/Neighbor to NULL.
For example, consider the network configuration shown in
Figure 4. When calculating the Area 1 datagram shortest-
path tree for a datagram whose source is Network N7 (e.g.,
from Host H5) and destination is Group Ma, Router RT2 would
initialize the candidate list to contain the two area border
routers RT3 (with a cost of 20) and RT4 (with a cost of 19).
See Figure 6 for more details.
12.2.3. Candidate list Initialization: Case SourceInterArea2
In this case, SourceNet belongs to an OSPF area other than
Area A, but one that is still directly attached to the
calculating router (RTX). The candidate list is then
initialized in the following two steps:
(1) Find the Area A summary-link-LSA that best matches
SourceNet, excluding those summary-link-LSAs specifying
cost LSInfinity or having unreachable Advertising
Routers[24]. A matching summary-link-LSA is one that
advertises a range of addresses containing SourceNet;
the best matching is as usual the most specific match.
Let SourceRange be the network described by the best
matching summary-link-LSA.
(2) Similar to the logic in the SourceInterArea1 case,
examine all the Area A summary-link-LSAs which advertise
SourceRange. For each such summary-link-LSA: if both a)
the MC-bit is set in the LSA's Options field, b) the
advertised cost is not equal to LSInfinity and c) the
Advertising Router is reachable, then the vertex
representing the LSA's Advertising Router is added to
the candidate list. An added vertex' state is
initialized as: IncomingLinkType set to ILSummary, Cost
to whatever is advertised in the LSA, Parent to NULL and
AssociatedInterface/Neighbor to NULL.
The reason why SourceRange is used, instead of simply using
SourceNet (as was done in case SourceInterArea1), is that
routing information may have been collapsed at area
boundaries. In order for Area A's area border routers and
its internal routers to construct the same Area A datagram
shortest-path tree, they must both start at SourceRange -
Area A's internal routers know nothing about SourceNet. Note
that SourceRange is not discovered simply by looking at the
calculating router's configured set of area address ranges,
in order to avoid dependence on the configured area address
ranges being synchronized across all area border routers.
For example, consider the network configuration shown in
Figure 4. When calculating the Area 2 datagram shortest-
path tree for a datagram whose source is Network N11 and
destination is Group Ma, Router RT11 would calculate
SourceRange to be the collection: Networks N9-N11 and Host
H1. It would then initialize the candidate list to contain
itself (RT11) only, with an associated Cost of 1 (since RT11
is advertising Networks N9-N11 and Host H1 in a summary-
link-LSA with a cost of 1).
12.2.4. Candidate list Initialization: Case SourceExternal
In this case, SourceNet is external to the OSPF routing
domain, and Area A is not an OSPF stub area. The candidate
list is then initialized as follows. Note that an attempt
may be made to add a Vertex W to the candidate list when W
already belongs to the candidate list. When this happens,
W's vertex parameters are updated if the Cost parameter it
would be added with is better[25] (closer to SourceNet) than
its previous value. When the costs are the same, W's
parameters are still modified if the IncomingLinkType it
would be added with is better (see IncomingLinkType's
definition in Section 12.1) than its previous value.
For each AS external-link-LSA advertising SourceNet, the
following steps are performed:
o If the AS external-link-LSA's MC-bit is clear or if its
advertising router is not reachable, then the AS
external-link-LSA is not used. AS external-link-LSAs
having their MC-bit set and advertising a cost of
LSInfinity can be used; these LSAs describe paths that
can be used for multicast, but not unicast, data traffic
(see Section 11.2).
o If the AS external-link-LSA's Forwarding address field
is 0.0.0.0, the following vertices are added to the
candidate list. If the Advertising AS boundary router
(call it ASBR) belongs to Area A, the vertex
representing the AS boundary router is added to the
candidate list using parameters: IncomingLinkType set to
ILExternal, Cost to whatever is advertised in the LSA,
Parent to NULL and AssociatedInterface/Neighbor to NULL.
Then, regardless of whether ASBR belongs to Area A, all
Area A area border routers that are advertising
reachable multicast-capable (MC-bit set) type 4
summary-link-LSAs for ASBR are added to the candidate
list. Each such area border router is added with the
parameters: IncomingLinkType set to ILSummary, Cost to
the sum of whatever is advertised in the type 4
summary-link-LSA plus the value in the original AS
external-link-LSA, Parent to NULL and
AssociatedInterface/Neighbor to NULL.
o If the AS external-link-LSA's Forwarding address field
is non-zero, the Forwarding address is looked up in the
OSPF routing table. Then processing breaks into one of
the following cases:
o The Forwarding address is not usable. In this case,
nothing is added to the candidate list. The
Forwarding address is not usable if either it has no
matching routing table entry, or if the matching
routing table entry is neither of type intra-area
nor of type inter-area.
o The Forwarding address belongs to Area A[26]: the
Forwarding address' matching routing table entry has
Path-type of intra-area and its Associated area is
Area A. In this case, the vertex represented by the
matching routing table entry's Link State Origin
field is added to the candidate list (assuming that
the vertex is multicast-capable). The vertex is
added with the parameters: IncomingLinkType set to
ILExternal, Cost to whatever was advertised in the
original AS external-link-LSA, Parent to NULL and
AssociatedInterface/Neighbor to NULL.
o The Forwarding address belongs to an area that is
not attached to Router RTX[27]: the Forwarding
address' matching routing table entry has Path-type
of inter-area. Call the network represented by the
matching routing table entry ForwardNet. For each
reachable multicast-capable summary-link-LSA (in
Area A) advertising ForwardNet, add the LSA's
advertising area border router to the candidate list
using parameters: IncomingLinkType set to ILSummary,
Cost to the sum of whatever is advertised in the
summary-link-LSA plus the value in the original AS
external-link-LSA, Parent to NULL and
AssociatedInterface/Neighbor to NULL.
o The Forwarding address belongs to another one of
Router RTX's attached areas[28]: the Forwarding
address' matching routing table entry has Path-type
of intra-area and its associated Area is other than
Area A. Call the network represented by the
matching routing table entry ForwardNet. First find
the Area A summary-link-LSA that best matches
ForwardNet, excluding those summary-link-LSAs
specifying cost LSInfinity or having unreachable
Advertising Routers. Let ForwardRange be the network
described by the best matching summary-link-LSA.
Then, for each reachable multicast-capable summary-
link-LSA (in Area A) advertising ForwardRange, add
the LSA's advertising area border router to the
candidate list using parameters: IncomingLinkType
set to ILSummary, Cost to the sum of whatever is
advertised in the summary-link-LSA plus the value in
the original AS external-link-LSA, Parent to NULL
and AssociatedInterface/Neighbor to NULL.
The above calculation can be restated as follows. Each of
Area A's inter-area multicast forwarders and inter-AS
multicast forwarders are examined. Those that have
multicast-capable paths to SourceNet (represented as either
a multicast-capable AS external link or the concatenation of
a Type 4 summary link and a multicast-capable AS external
link) are added to the candidate list as router vertices.
(It is possible that, when considering a router that is both
an inter-area multicast forwarder and an inter-AS multicast
forwarder, two equal cost paths exist to SourceNet, one an
AS external link and the other a concatenation of a Type 4
summary link and an AS external link. In this case, the
concatenation of the Type 4 summary link and the AS external
link is preferred). The added vertex' state is set as
follows: IncomingLinkType set to ILSummary if the path is
represented as a concatenation of a Type 4 summary link and
an AS external link, IncomingLinkType set to ILExternal
otherwise, Cost set to the cost of the shortest path from
vertex to SourceNet, Parent set to NULL and
AssociatedInterface/Neighbor set to NULL.
For example, consider the network configuration shown in
Figure 4. When calculating the Area 2 datagram shortest-
path tree for a datagram whose source is Network N14 and
destination is Group Ma, the candidate list would be
initialized to the two routers RT7 at a cost of 14 and RT10
at a cost of 19. This assumes that the external costs
pictured in Figure 4 are external type 1s.
12.2.5. Candidate list Initialization: Case
SourceStubExternal
In this case, SourceNet is external to the OSPF routing
domain, and Area A is an OSPF stub area. The candidate list
is then initialized similarly to case SourceInterArea1. The
Area A summary-link-LSAs advertising DefaultDestination are
examined. For each such summary-link-LSA having both its
MC-bit set and its advertised cost not equal to LSInfinity,
the vertex representing the LSA's advertising area border
router is added to the candidate list. An added vertex'
state is initialized as: IncomingLinkType set to ILSummary,
Cost to whatever is advertised in the LSA, Parent to NULL
and AssociatedInterface/Neighbor to NULL.
The most likely outcome of the above is that all of stub
Area A's inter-area multicast forwarders will be installed
on the candidate list, with appropriate costs.
12.2.6. Processing labelled vertices
When encountered during the SPF calculation, vertices
labelled with the destination multicast group (Group G) may
cause the forwarding cache entry's list of downstream
interfaces/neighbors to be modified. A Vertex V in Area A
is labelled with Group G if and only if at least one of the
following holds:
(1) V is a router, and its router-LSA indicates that it is a
wild-card multicast receiver (i.e., bit W in its
router-LSA is set). This may be true when V is an
inter-area or inter-AS multicast forwarder.
(2) V is listed in the body of a group membership-LSA. In
particular, find the originator of Vertex V's LSA; call
it Router Y. Then find the group-membership-LSA in Area
A's link state database which has Link State ID = Group
G and Advertising Router = Router Y (see Section A.3).
If this group-membership-LSA exists, and if Vertex V is
listed in the body of the LSA (see Sections 10 and A.3),
then Vertex V is labelled with Group G.
When Vertex V is added to the shortest-path tree in Step 4
of Section 12.2, and if Vertex V is both downstream from the
calculating router (i.e., Vertex V's
AssociatedInterface/Neighbor is non-NULL) and labelled with
Group G, then Vertex V's AssociatedInterface/Neighbor is
added to the forwarding cache entry's list of downstream
interfaces/neighbors. In addition, Vertex V's TTL value is
attached to the added downstream interface/neighbor. If the
particular interface/neighbor had already been added to the
list of downstream interfaces/neighbors, the list is simply
modified by setting the downstream interface/neighbor's TTL
value to the minimum of its existing TTL value and Vertex
V's TTL value.
12.2.7. Merging datagram shortest-path trees
After the datagram shortest-path tree for Area A is
complete, the calculating router (RTX) must decide whether
Area A, out of all of its attached areas, determines the
forwarding cache entry's upstream node. This is done by
examining RTX's position on the Area A datagram shortest-
path tree, which is in turn described by RTX's Area A Vertex
data structure. If RTX's Vertex parameter IncomingLinkType
is either ILNone (RTX is not on the tree), ILVirtual or
ILSummary, then some area other than Area A will determine
the upstream node. Otherwise, Area A might possibly
determine the upstream node (i.e., may be selected the
RootArea), depending on the following tiebreakers[29]:
o If RootArea has not been set, then set RootArea to Area
A. Otherwise, compare the present RootArea to Area A in
the following:
o Choose the area that is "nearest to the source". Nearest
to the source depends on each area's candidate list
initialization case, as it occurs in Step 2 of Section
12.2. The initialization cases, listed in order of
decreasing preference (or nearest to farthest) are:
SourceIntraArea, SourceInterArea1, SourceExternal and
SourceStubExternal. Areas whose candidate list
initialization falls into case SourceInterArea2 are
never used as the RootArea. As an example, consider the
network configuration shown in Figure 4. When
calculating the datagram shortest-path tree for a
datagram whose source is Network N7 (e.g., from Host H5)
and destination is Group Ma, Router RT11 would set its
RootArea to Area 2 (Case SourceIntraArea) instead of
Area 3 (Case SourceInterArea2) or the backbone Area 0
(Case SourceInterArea).
o If there are still two equally good areas, and one of
them is the backbone, set RootArea to the backbone (Area
0).
o If there are still two equally good areas, set RootArea
to the area whose datagram shortest-path tree provides
the shortest path from SourceNet to RTX. This is a
comparison of RTX's Vertex parameter Cost in the two
areas.
o If there are still two equally good areas, set RootArea
to one with the highest OSPF Area ID.
If the above has set the RootArea to be Area A, the
forwarding cache entry's upstream node must be set
accordingly. This setting depends on the IncomingLinkType in
RTX's Area A Vertex structure. If IncomingLinkType is equal
to ILDirect, the upstream node is set to the appropriate
directly-connected stub network. If equal to ILNormal, the
upstream node is set to the Parent field in RTX's Area A
Vertex structure. If equal to ILExternal, the upstream node
is set to the placeholder EXTERNAL.
12.2.8. TOS considerations
The previous sections 12.2 through 12.2.7 described the
construction of a TOS 0 (default TOS) datagram shortest-path
tree. However, in a TOS-capable router, a separate tree may
be built for each TOS. If a TOS-capable router receives a
multicast datagram that specifies a non-zero TOS X, it first
builds the TOS 0 datagram shortest-path tree. Then, if all
the routers on the pruned tree are TOS-capable, a separate
TOS X datagram shortest-path tree is calculated[30].
Otherwise, the TOS 0 tree is used for all datagrams,
regardless of their specified TOS.
To determine whether there are any TOS-incapable routers on
the pruned TOS 0 tree, the following additions are made to
Section 12.2's tree calculation:
o A new piece of state information is added to each
vertex: TOS-capable path. This indicates whether the
present path from SourceNet to vertex, as represented on
the datagram shortest-path tree, contains only TOS-
capable routers.
o The TOS-capable path parameter is calculated when the
vertex is first added to the candidate list and
recalculated when/if the vertex' position on the
candidate list is modified (see Section 12.2's Step 2
and Step 5d). The parameter is set to TRUE if both the
vertex itself is TOS-capable and the vertex' parent has
its TOS-capable path parameter set to TRUE; otherwise,
TOS-capable path is set to FALSE.
o All routers on the TOS 0 datagram shortest-path tree are
TOS-capable if and only if, whenever a vertex labelled
with Group G is added to the shortest-path tree (Section
12.2.6), the value of the vertex' TOS-capable path
parameter is TRUE.
The source of the multicast datagram is always located using
a TOS 0 routing table lookup, regardless of the datagram's
TOS classification (see Section 11.2). If the calculating
router is not capable of TOS-based routing, it calculates
only TOS 0 datagram shortest-path trees, and uses them to
route datagrams independent of TOS value. Otherwise, when
calculating the TOS X datagram shortest-path tree, the
algorithm in Section 12.2 is used, with the modifications
listed below.
o When calculating RangeNet and ForwardRange in Sections
12.2.3 and 12.2.4 respectively, only summary-link-LSAs
having TOS 0 cost of LSInfinity are excluded (no change
from the TOS 0 case). However, when adding vertices to
the candidate list in Sections 12.2.2 through 12.2.5,
the TOS X cost of the summary links and/or AS external
links (and not the TOS 0 cost) are reflected in the
added vertices' Cost parameter.
o In Step 5 of Section 12.2, the TOS X cost of Link L (in
the appropriate direction) is used, not the TOS 0 cost.
o Non-TOS-routers are not added to the candidate list, and
are thus excluded from the trees.
12.2.9. Comparison to the unicast SPF calculation
There are many similarities between the construction of a
multicast datagram's shortest-path trees in Section 12.2 and
OSPF's intra-area route calculation for unicast traffic
(Section 16.1 of [OSPF]). Both have been described in terms
of Dijkstra's algorithm. However, there are some
differences. The major differences are listed below:
o In the multicast case, the datagram SPF calculation is
rooted at the datagram's source. In the unicast case,
each router is the root of its own unicast intra-area
SPF calculation.
o In the multicast case, the datagram shortest-path tree
is a true tree; i.e., between any two nodes on the tree
there is one path. However, due to the provision for
equal-cost multipath in [OSPF], the unicast SPF
calculation may add additional links to the shortest-
path tree.
o In order to avoid unwanted replication of multicast
datagrams, MOSPF ensures that, for any given datagram,
each router builds the exact same datagram shortest-path
tree. This forces two differences from the unicast SPF
calculation. First, it eliminates the possibility of
equal-cost multipath. Secondly, when the MOSPF system
contains multiple alternate paths, the algorithm must
ensure that each MOSPF router deterministically chooses
the same alternative. For this reason, tie-breaking
mechanisms have been specified in Steps 2, 4 and 5b of
Section 12.2.
o The calculation of datagram shortest path trees takes
into account only those links that connect transit nodes
(i.e, router to router or router to transit network
links). The unicast SPF calculation in Section 16.1 of
[OSPF] must additionally examine links to stub networks,
although this is done after all the transit links are
examined.
o While both the multicast and unicast trees select
shortest paths on the basis of the OSPF metric, the
datagram shortest-path trees also keep track of the TTL
values between the root (datagram source) and all
destinations (group members). This enables more
efficient implementation of IP multicast's "expanding
ring search" (see Section 2.3.4).
o In the multicast case, the algorithm is sometimes forced
to use the link state cost for the reverse direction
(i.e, the cost towards, instead of away from, the
source). This is because the costs of OSPF summary-
link-LSAs and AS external-link-LSAs, which sometime form
the base of the multicast datagram shortest-path trees,
are specified in the reverse direction (from the
multicast perspective).
o There are potentially many more datagram shortest-path
trees that need to be calculated (one for each source
net, destination group and TOS combination), than the
limited number of unicast SPF trees (one per each TOS).
This is the main reason that the datagram shortest-path
trees are calculated on demand; it is hoped that this
will spread the cost of the SPF calculations over
time[31].
o The way that the two algorithms handle TOS is different.
In the multicast case, if a TOS-incapable node is
encountered during the calculation of the TOS 0 datagram
shortest-path tree, the TOS 0 datagram shortest-path
tree is used instead of trying to build the TOS X tree
(see Section 12.2.8). In the unicast case, the TOS X
tree is always used, only falling back on the TOS 0
paths when a TOS X path does not exist.
12.3. Adding local database entries to the forwarding cache
After the datagram shortest-path trees have been built for each
attached area, the forwarding cache has an upstream node and a
list of downstream interfaces. In order to ensure the delivery
of the multicast datagram to group members on directly attached
networks, the local group database (Section 8.4) must then be
scanned for possible addition to the list of downstream
interfaces. All local group database entries having Group G as
MulticastGroup are examined. Suppose [Group G, Network N] is
one such entry. If the calculating router (RTX) is Network N's
Designated Router, then RTX's Network N interface is added to
the list of outgoing interfaces, with a TTL of 1. If the Network
N interface was already present in the list of outgoing
interfaces, its TTL is simply set to 1.
For example, consider the network configuration shown in Figure
4 when calculating the forwarding cache entry for a datagram
whose source is Network N4 (e.g., from Host H2) and destination
is Group Mb. After calculating the datagram shortest-path tree
for Area 1, Router RT2 would have set it upstream node to
Network N3 and its list of downstream interfaces to NULL. But
then looking at its local group database, it would add its
Network N2 interface with a TTL of 1 to its list of downstream
interfaces.
(page 76 continued on part 4)