timer is disabled and no more Hosts Membership Queries are sent.
Unusual behavior can result when multiple IP networks are
assigned to a single physical network. MOSPF treats each such IP
network separately, electing (possibly) a different Designated
Router for each network. However, IGMP operates on a physical
network basis only: when a Host Membership Query is sent, all
group members on the physical network respond, regardless of
their IP addresses. So unless the IPMulticastForwarding
parameter is set to a value other than data-link multicast on
all but one of the physical network's IP networks, excess
multicast membership reporting will result.
9.2. Receiving IGMP Host Membership Reports
Received Host Membership Reports are processed by both the
network's Designated Router and Backup Designated Router. It is
the Designated Router's responsibility to distribute the
network's group membership information throughout the routing
domain, by originating group-membership-LSAs (see Section 10).
The Backup Designated Router processes Reports so that it too
has a complete picture of the network's group membership,
enabling a quick cutover upon Designated Router failure.
An IGMP Host Membership Report concerns membership in a single
IP multicast group (call it Group A). The Report is sent to the
Group A address so that other group members may see the Report
and avoid sending duplicates (see [RFC1112] for details). When
an IGMP Host Membership Report, sent on Network N[14], is
received by a MOSPF router, the following steps are executed:
(1) If the router is neither the Designated Router nor the
Backup Designated Router on the network, the Report is
discarded and processing stops.
(2) If the Report concerns a multicast group in the range
224.0.0.1 - 224.0.0.255, the Report is discarded and
processing stops. This range of multicast groups are for
local use (single hop) only, and datagrams sent to these
destinations are never forwarded by multicast routers.
(3) Locate the entry for [Group A, Network N] in the local group
database. If no such entry exists, create one. In any case,
set the age of the entry to 0. Note that even if multiple
hosts attached to Network N report membership in the same
group, only a single local group database entry will be
formed. See Section 8.4 for more details concerning the
local group database.
(4) If the router is the network's Designated Router, and a
local group database entry was created in the previous step,
it may be necessary to originate a new group-membership-LSA.
See Section 10 for details.
9.3. Aging local group database entries
Every local database entry has an age field. Suppose that there
is a database entry for [Group A, Network N1]. The age field
then indicates the length of time (in seconds) since the last
Host Membership Report for Group A was received on Network N1.
If the age of the entry reaches Network N1's configured
IGMPTimeout value (see Section B.2), the entry is considered
invalid and is removed from the database.
Note that when a router, after having been either Network N1's
Designated Router or Backup Designated Router, but now being
neither, will (after IGMPTimeout seconds) automatically age out
all of its local group database entries associated with Network
N1. For this reason, it is not necessary to purge local group
database entries on OSPF interface state changes.
9.4. Receiving IGMP Host Membership Queries
If a MOSPF router has internal multicast applications, and if
the applications have bound themselves to certain interfaces
(using the RFC1112 representation described in Section 5), then
the MOSPF router responds to received Host Membership Queries by
issuing Host Membership Reports. Identical to the operation of
any IP host supporting multicast applications, the exact
procedure for issuing these Host Membership Reports is specified
in [RFC1112]. Note that in this case, if the router has been
elected Designated Router on a network, it must receive its own
Host Membership Reports and Host Membership Queries.
If instead all of its applications have joined groups in an
interface-independent fashion (using the MOSPF-specific
representation described in Section 5), the MOSPF router does
not respond to Host Membership Queries. Instead, the MOSPF
router communicates this membership information by originating
appropriate group-membership-LSAs (see Section 10.1).
10. Group-membership-LSAs
Group-membership-LSAs provide the means of distributing membership
information throughout the MOSPF routing domain. Group-membership-
LSAs are specific to a single OSPF area (see Section 3.1). Each
group-membership-LSA concerns a single multicast group. Essentially,
the group-membership-LSA lists those networks which are directly
connected to the LSA's originator and which contain one or more
group members. For more details on how the group-membership-LSA
augments the OSPF link state database, see Section 2.3.1.
The creation of group-membership-LSAs is discussed in Section 10.1.
The format of the group-membership-LSA is described in Section A.3.
A router will originate a group membership-LSA for multicast group A
when one or more of the following conditions hold:
(1) The router is Designated Router on a network (call it Network
X), the interface to Network X has its IPMulticastForwarding
parameter set to data-link multicast (see Section B.2), and
Network X contains one or more members of Group A.
(2) The router is an inter-area multicast forwarder (see Section
B.1), and one or more of the router's attached non-backbone
areas contain Group A members. In this case, the router will
originate a group-membership-LSA for Group A into the backbone.
This is the way group membership is conveyed between areas (see
Section 3.1).
(3) The router itself has applications that are requesting
membership in Group A, in an interface-independent fashion (see
Section 5).
As for all other types of OSPF link state advertisements (e.g,
router-LSAs, network-LSAs, etc.), group-membership-LSAs are aged as
they are held in a router's link state database. To prevent valid
advertisements from "aging out", a router must refresh its self-
originated group-membership-LSAs every LSRefreshTime interval, by
incrementing their LS sequence numbers and reissuing them. In
addition, when an event occurs that would alter one of the router's
self-originated group-membership-LSAs, a new instance of the LSA is
issued with an updated (i.e., incremented by 1) LS sequence number.
Note however that a router is not allowed to originate two new
instances of the same advertisement within MinLSInterval seconds.
For that reason, occasionally advertisement originations will need
to be deferred. Also, an event may occur that makes it inappropriate
for the router to continue to originate a particular LSA. In that
case, the router flushes the advertisement from the routing domain
by "premature aging". For more information concerning the
maintenance of LSAs, see Sections 12, 12.4, 14 and 14.1 of [OSPF].
When one of the following events occurs, it may be necessary for a
router to (re)issue one or more group-membership-LSAs:
(1) One of the router's interfaces changes state. For example, the
router may have become Designated Router on a particular
network, causing the router to start advertising the network's
group membership to the rest of the MOSPF system in group-
membership-LSAs.
(2) The router receives an IGMP Host Membership Report, causing a
new local group database entry to be formed (see Section 9.2).
(3) One of the router's local group database entries "ages out",
because it is no longer being refreshed by received IGMP Host
Membership Reports (see Section 9.3).
(4) The router is an inter-area multicast forwarder, and the group
membership of one of the router's attached non-backbone areas
changes. This is detected by the reception of a new, or the
flushing of an old, group-membership-LSA into/from the non-
backbone area's link state database.
(5) The group membership of one of the router's internal
applications changes.
10.1. Constructing group-membership-LSAs
This section details how to build a group-membership-LSA. The
format of a group-membership-LSA is described in Section A.3.
Each group-membership-LSA concerns a single multicast group. The
body of the advertisement is a list of the local transit nodes
(the router itself and directly attached transit networks) that
contain group members. Section 10 listed the conditions
requiring the (re)origination of a group-membership-LSA. Note
that if the router is an area border router, it may be necessary
to originate a separate group-membership-LSA for each attached
area.
The following defines the contents of a group-membership-LSA, as
originated by Router X into Area A. It is assumed that the
group-membership-LSA is to report membership in multicast group
G:
o The advertisement fields that are not type-specific (LS age,
LS sequence number, LS checksum and length) are set
according to Section 12.1 of [OSPF].
o The Options field of a group-membership-LSA is not processed
on receipt. However, for consistency, the Option field in
these advertisements should have its MC-bit set, T-bit
clear, and the E-bit should match the configuration of Area
A (i.e., set if and only if Area A is not a stub area). The
rest of the Options field is set to 0.
o The Link State ID is set to the group whose membership is
being reported (Group G).
o The Advertising Router is set to the OSPF Router ID of the
router originating the advertisement (Router X).
o The body of the advertisement is a list of local transit
vertices that should be labelled with Group G membership
(see Section 2.3.1). This list may include the advertising
router itself, and any of the transit networks that are
directly attached to said router. The following steps
determine which of these transit vertices are actually
included in the group-membership-LSA. Note that any
particular vertex should be listed at most once, even though
the following may indicate multiple reasons for a particular
vertex to be listed. Also note that if no transit vertices
are listed by the advertisement, the advertisement should
not be (re)originated; if an instance of the advertisement
already exists, it should then be flushed from the link
state database using the premature aging procedure specified
in Section 14.1 of [OSPF].
a. Consider those entries in the local group database that
describe Group G membership (see Section 8.4). Consider
each such entry in turn. Each entry references one of
Router X's attached networks (call it Network N). If
either Network N does not belong to Area A, or if Router
X is not Network N's Designated Router[15], Network N
should not be added to the group-membership-LSA, and the
next local group database entry should be examined.
Otherwise, if N is a stub network (e.g., Router X is the
only OSPF router attached to N), Router X adds itself to
the advertisement by adding a vertex with Vertex type
set to 1 (router) and Vertex ID set to Router X's OSPF
Router ID. Otherwise, N is a transit network. In this
case, Network N should be added to the advertisement by
adding a vertex with Vertex type set to 2 (network) and
Vertex ID set to the IP address of Network N's
Designated Router (i.e., Router X's IP interface address
on Network N).
b. If Router X itself has applications requesting Group G
membership on an interface-independent basis (see
Section 5), it should add itself to the advertisement by
adding a vertex with Vertex type set to 1 (router) and
Vertex ID set to Router X's OSPF Router ID.
c. If Router X is an inter-area multicast forwarder (see
Section 3.1), Area A is the backbone area (Area ID
0.0.0.0), and at least one of Router X's attached non-
backbone areas has Group G members (indicated by the
presence of one or more advertisements in the areas'
link state databases having Link State ID set to Group G
and LS age set to a value other than MaxAge[16]), then
Router X should add itself to the advertisement by
adding a vertex with Vertex type set to 1 (router) and
Vertex ID set to Router X's OSPF Router ID.
Consider as an example the network configuration in Figure 4.
Suppose that Router RT2 has been elected Designated Router for
Network N3. Router RT2 would then originate (into Area 1) the
following group-membership-LSA for Group B:
; RT2's group-membership-LSA for Group B
LS age = 0 ;always true on origination
Options = (E-bit|MC-bit)
LS type = 6 ;group-membership-LSA
Link State ID = Group B
Advertising Router = RT2's Router ID
Vertex type = 1 ;RT2 itself (for stub N2)
Vertex ID = RT2's Router ID
Vertex type = 2 ;Network N3 (since RT2 is DR)
Vertex ID = RT2's IP interface address on N3
10.2. Flooding group-membership-LSAs
When MOSPF routers and non-multicast OSPF routers are mixed
together in a routing domain, the group-membership-LSAs are not
flooded to the non-multicast routers[17]. As a general design
principle, optional OSPF advertisements are only flooded to
those routers that understand them.
A MOSPF router learns of its neighbor's multicast-capability at
the beginning of the "Database Exchange Process" (see Section
10.6 of [OSPF], receiving Database Description packets from a
neighbor in state Exstart). A neighbor is multicast-capable if
and only if it sets the MC-bit in the Options field of its
Database Description packets. Then, in the next step of the
Database Exchange process, group-membership-LSAs are included in
the Database summary list sent to the neighbor (see Sections 7.2
and 10.3 of [OSPF]) if and only if the neighbor is multicast-
capable.
When flooding group-membership-LSAs to adjacent neighbors, a
MOSPF router looks at the neighbor's multicast-capability.
Group-membership-LSAs are only flooded to multicast-capable
neighbors. To be more precise, in Section 13.3 of [OSPF],
group-membership-LSAs are only placed on the Link state
retransmission lists of multicast-capable neighbors[18]. Note
however that when sending Link State Update packets as
multicasts, a non-multicast neighbor may (inadvertently) receive
group-membership-LSAs. The non-multicast router will then simply
discard the LSA (see Section 13 of [OSPF], receiving LSAs having
unknown LS types).
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 [RFC1112]
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 [RFC1390] for details.
o On SMDS networks, the datagram is forwarded using the same
SMDS address that is used by IP broadcast datagrams. See
[RFC1209] 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 [RFC1112] 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 [RFC1112].
(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 -