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.
13. Maintaining the forwarding cache
A MOSPF router may, for resource reasons, limit the size of its
forwarding cache. At any time cache entries can be purged to make
room for newer entries, since the purged entries can always be
rebuilt when necessary. This memo does not specify an algorithm to
select which entries to purge. However, care should be taken to
ensure that any particular entry is not continually rebuilt and then
purged again (i.e., thrashing should be avoided).
The building of the forwarding cache has been previously described
in Section 12. There are events that force one or more forwarding
cache entries to be deleted; these events are described below. Note
that deleted cache entries will be rebuilt on an as-needed basis.
o When the internal topology of the MOSPF system changes, all
forwarding cache entries must be deleted. This is because
internal topology changes may invalidate the previously
calculated datagram shortest-path trees. Since the multicast
routing calculation depends on the result of the unicast routing
calculations, the forwarding cache should be cleared after the
unicast routing table is rebuilt. Internal topology changes are
indicated when both a) a new instance of either a router-LSA or
a network-LSA is received and b) the contents of the new
advertisement (other than the LS age, LS sequence number and LS
checksum fields) are different from the previous instance. This
covers routers and links going up or down, routers that change
from being multicast-incapable to being multicast-capable, etc.
o When a Type 3 summary-link-LSA (network summary) changes, those
forwarding cache entries specifying datagram sources belonging
to the range of addresses described by the updated summary-
link-LSA must be deleted. See Sections 12.2.3 and 12.2.5.
o Suppose that the content of an AS external-link-LSA changes. If
the AS external-link-LSA describes an external network N, then
all forwarding cache entries specifying an external source
network that is contained in N or that contains N (i.e.,
external sources that are a subset or a superset of N) must be
deleted.
o When membership in a multicast group changes, all forwarding
cache entries for the particular group must be deleted. Group
membership changes are indicated when either a) the content of a
group-membership-LSA changes or b) an entry in the local group
database (see Section 8.4) changes.
o When the cost to an AS boundary router or to a forwarding
address specified by one or more AS external-link-LSAs changes,
all forwarding cache entries specifying an external network as
datagram source must be deleted. In this case, potentially all
inter-AS datagram shortest-path trees have been invalidated. The
forwarding cache entries should be deleted after the new best
cost to the AS boundary router/forwarding address has been
calculated.
14. Other additions to the OSPF specification
MOSPF requires some modifications to the base OSPF protocol. All
these modifications are backward-compatible. A router running MOSPF
will still interoperate with an OSPF router when forwarding unicast
traffic. Most of the modifications have been described earlier in
this document. This section collects together those changes which
have yet to be mentioned, organizing them by the affected Section of
[OSPF].
14.1. The Designated Router
This functionality is described in Section 7.3 of [OSPF]. In
OSPF, a network's Designated Router has two specialized roles.
First, it originates the network's network-LSA. Second, it
controls the flooding on the network, in that all of the routers
on the network synchronize with the Designated Router (and the
Backup Designated Router) only. For these reasons[32], when one
or more of the network's routers are running MOSPF, the
Designated Router should be running MOSPF also. This can be
ensured by assigning all non-multicast routers the Router
Priority of 0.
In MOSPF, the Designated Router also has the additional
responsibility of monitoring the network's multicast group
membership. This is done by periodically sending Host Membership
Queries, and receiving Host Membership Reports in response (see
Section 9). This is yet another reason why the Designated Router
must be multicast-capable.
14.2. Sending Hello packets
This functionality is described in Section 9.5 of [OSPF]. A
MOSPF router sets the MC-bit in the Options field of its Hello
packets. This indicates that the router is multicast-capable; it
does not necessarily indicate the state of the sending
interface's IPMulticastForwarding parameter (see Section B.2).
Setting the MC-bit in Hellos is done strictly for informational
purposes. Neighbors receiving the router's Hello packets do not
act on the state of the MC-bit. A neighbor's multicast-
capability is learned instead during the Database Exchange
Process (see Section 14.4).
14.3. The Neighbor state machine
This functionality is described in Section 10.3 of [OSPF]. When
a neighbor enters state Exchange, the neighbor Database summary
list is initialized (see the OSPF neighbor FSM entry for State:
ExStart and Event: NegotiationDone). This list describes of the
portion of the router's link state database that needs to be
synchronized with the neighbor. Group-membership-LSAs are
included in the neighbor Database summary list if and only if
the neighbor is multicast-capable. The neighbor's multicast
capability is learned by examining the neighbor's Database
Description packets (see Section 14.4).
14.4. Receiving Database Description packets
This functionality is described in Section 10.6 of [OSPF]. A
neighbor's multicast-capability is learned through received
Database Description packets. When the Database Description
packet is received that transitions the neighbor from ExStart to
Exchange, the state of the MC-bit in the packet's Options field
is examined. The neighbor is multicast-capable if and only if
the MC-bit is set.
The neighbor's multicast capability controls whether group-
membership-LSAs are summarized to the neighbor during the
Database Exchange process (see Section 14.3), and whether
group-membership-LSAs are flooded to the neighbor during the
flooding process (see Section 10.2).
14.5. Sending Database Description packets
This functionality is described in Section 10.8 of [OSPF]. A
MOSPF router sets the MC-bit in the Options field of its
Database Description packets. This indicates to its adjacent
neighbors that the router is multicast-capable; it does not
necessarily indicate the state of the sending interface's
IPMulticastForwarding parameter (see Section B.2).
When a router goes from being multicast-capable to multicast-
incapable, or vice-versa, it must indicate this fact to its
adjacent neighbors by restarting the Database Description
process (i.e., rolling back the state of all adjacent neighbors
to Exstart).
14.6. Originating Router-LSAs
This functionality is described in Section 12.4.1 of [OSPF]. A
MOSPF router sets the MC-bit in the Options field of its
router-LSA. This allows the router to be included in datagram
shortest-path trees (see Step 5a of Section 12.2).
In addition, MOSPF has introduced a new flag in the router-LSA's
rtype field: the W-bit. When the W-bit is set, the router is
included on all datagram shortest-path trees, regardless of
multicast group (see Section 12.2.6). Such a router is called a
wild-card multicast receiver. The router sets the W-bit when it
wishes to receive all multicast datagrams, regardless of
destination. This will sometimes be true of inter-area multicast
forwarders (see Section 3.1), and inter-AS multicast forwarders
(see Section 4).
A router must originate a new instance of its router-LSA
whenever an event occurs that would invalidate the LSA's current
contents. In particular, if the router's multicast capability or
its ability to function as either an inter-area or inter-AS
multicast forwarder changes, its router-LSA must be
reoriginated.
14.7. Originating Network-LSAs
This functionality is described in Section 12.4.2 of [OSPF]. In
OSPF, a transit network's network-LSA is originated by the
network's Designated Router. The Designated Router sets the MC-
bit in the Options field of the network-LSA if and only if both
a) the Designated Router is multicast-capable (i.e., running
MOSPF) and b) the Designated Router's interface's
IPMulticastForwarding parameter has been set to a value other
than disabled (see Section B.2). When the network-LSA has the
MC-bit set, the network can be included in datagram shortest-
path trees (see Section 12.2.6).
It is intended that all routers attached to a common network
agree on the network's IPMulticastForwarding capability.
However, this agreement is not enforced. When there are
disagreements, incorrect routing of multicast datagrams can
result.
14.8. Originating Summary-link-LSAs
This functionality is described in Section 12.4.3 of [OSPF].
Inter-area multicast forwarders always set the MC-bit in the
Options field of their summary-link-LSAs, regardless of whether
the path described by the summary-link-LSA is actually
multicast-capable. Indeed, it is possible that there is no
multicast-capable path to the described destination. All other
area border routers (ones that are not inter-area multicast
forwarders) clear the MC-bit in the Options field of their
summary-link-LSAs.
If its MC-bit is clear, the summary-link-LSA will not be used
when initializing the candidate list in Sections 12.2.2, 12.2.3
and 12.2.5.
14.9. Originating AS external-link-LSAs
This functionality is described in Section 12.4.4 of [OSPF].
Unlike in summary-link-LSAs, an inter-AS multicast forwarder
should clear the MC-bit in the Options field of one of its AS
external-link-LSAs if it is known that there is no multicast-
capable path from the described destination to the router
itself. This knowledge may possibly be obtained, for example,
from an inter-AS multicast routing algorithm (see Section 4).
If the inter-AS multicast forwarder is unsure of whether a
multicast-capable path exists between the described destination
and the router itself, the MC-bit should be set in the AS
external-link-LSA. All other AS boundary routers (ones that are
not inter-AS multicast forwarders) clear the MC-bit in the
Options field of their AS external-link-LSAs.
If its MC-bit is clear, the AS external-link-LSA will not be
used when initializing the candidate list in Section 12.2.4.
When multicast connectivity to an external destination exists,
but no unicast connectivity, an AS external-link-LSA can be
originated having its MC-bit set and specifying a cost of
LSInfinity. Such an AS external-link-LSA will still be used by
the multicast routing calculation (see Section 12.2.4). As a
result, when a MOSPF router wishes to stop advertising an AS
external destination, it must use the premature aging procedure
specified in Section 14.1 of [OSPF], rather than simply setting
the AS external-link-LSA's cost to LSInfinity.
14.10. Next step in the flooding procedure
This functionality is described in Section 13.3 of [OSPF].
Group-membership-LSAs are specific to a OSPF single area, and
are flooded to multicast-capable routers only. When flooding a
group-membership-LSA, Section 13.3 of the OSPF specification is
modified as follows: 1) The list of interfaces examined during
flooding (called the eligible interfaces in Section 13.3 of
[OSPF]) is the set of all interfaces attaching to Area A (the
area that the group-membership-LSA is received from), just as
for router-LSAs, network-LSAs and summary-link-LSAs. 2) When
examining each interface, a group-membership-LSA is added to a
neighbor's link state retransmission list if and only if both a)
Step 1d of [OSPF]'s Section 13.3 is reached for the neighbor and
b) the neighbor is multicast-capable. The neighbor's multicast
capability is discovered during the Database Exchange process
(see Section 14.4).
Note that, since on broadcast networks Link State Update packets
are sent initially as multicasts, non-multicast routers may
receive group-membership-LSAs. However, non-multicast routers
will simply drop the group-membership-LSAs, for reasons of
unrecognized LS type (see Step 2 of [OSPF]'s Section 13). Link
State acknowledgments for group-membership-LSAs are not expected
from non-multicast routers, and group-membership-LSAs will never
be retransmitted to non-multicast routers, since the LSAs are
not added to these routers' link state retransmission lists (see
above paragraph).
For more information on flooding group-membership-LSAs, see
Section 10.2.
14.11. Virtual links
This functionality is described in Section 15 of [OSPF]. When a
MOSPF router (i.e., multicast-capable router) is both an area
border router and an endpoint of a virtual link whose other
endpoint is also multicast capable, the router must then also be
an inter-area multicast forwarder. This is necessary to ensure
that multicast datagrams will flow through the virtual link's
transit area, from one endpoint to the other. When the
backbone's datagram shortest-path tree is constructed in Section
12.1, it is assumed that virtual links are capable of forwarding
multicast datagrams whenever both endpoints are multicast-
capable.
15. References
[Bharath-Kumar] Bharath-Kumar, K. and J. Jaffe, "Routing to Multiple
Destinations in Computer Networks", IEEE
Transactions on Communications, COM-31[3], March
1983.
[Deering] Deering, S., "Multicast Routing in Internetworks and
Extended LANs", SIGCOMM Summer 1988 Proceedings,
August 1988.
[Deering2] Deering, S., "Multicast Routing in a Datagram
Internetwork", Stanford Technical Report, STAN-CS-
92-1415, Department of Computer Science, Stanford
University, December 1991.
[OSPF] Moy, J., "OSPF Version 2", RFC1583, Proteon, Inc.,
March 1994.
[RFC1075] Waitzman, D., Partridge, C., and S. Deering,
"Distance Vector Multicast Routing Protocol", RFC
1075, BBN STC, Stanford University, November 1988.
[RFC1112] Deering, S., "Host Extensions for IP Multicasting",
STD 5, RFC1112, Stanford University, May 1988.
[RFC1209] Piscitello, D., and J. Lawrence, "Transmission of IP
Datagrams over the SMDS Service", RFC1209, Bell
Communications Research, March 1991.
[RFC1340] Reynolds, J. and J. Postel, "Assigned Numbers", STD
2, RFC1340, USC/Information Sciences Institute,
July 1992.
[RFC1390] Katz, D., "Transmission of IP and ARP over FDDI
Networks", STD 36, RFC1390, cisco Systems, Inc.,
January 1993.
Footnotes
[1]Actually, OSPF allows a separate link cost to be configured for
each TOS. MOSPF then potentially calculates separate paths for each
TOS. For details, see Section 6.2.
[2]We also assume in this section that the pictured multi-access
networks provide data-link multicast/broadcast services.
[3]Note that if N3 were a non-broadcast network, Router RT3 would
send separate copies of the datagram to routers RT1 and RT2. Since
the IGMP protocol is not defined on non-broadcast networks, there
could in this case be no Group B member attached to Network N3.
However the multicast datagram would still be delivered to the Group
B members attached to networks N1 and N2.
[4]Actually, in MOSPF there is a separate forwarding cache entry for
each combination of source, destination and TOS. For a discussion of
TOS-based multicast routing, see Section 6.2.
[5]The discussion in this section omits mention of the Backup
Designated Router's role in the IGMP protocol. While the Backup
Designated Router does not send IGMP Host Membership Queries, it
does listen to IGMP Host Membership Reports, building "shadow" local
group database entries in the process. These entries do not lead to
group-membership-LSAs, nor do they influence delivery of multicast
datagrams, but are merely maintained to ease the transition from
Backup Designated Router to Designated Router, should the Designated
Router fail. See Sections 2.3.4, 9 and 10 for details.
[6]One might imagine building all possible datagram shortest-path
trees up front. However, this might be expensive, both in router CPU
time and in router memory. It is hoped that building the datagram
shortest-path trees on demand and caching the results will ease
demands on router resources by spreading out the calculations over a
longer period of time.
[7]It is possible that, due to the existence of alternate paths,
several different shortest-path trees are available. MOSPF depends
on all routers constructing the exact same shortest path tree. For
that reason, tie-breaking schemes have been implemented during tree
construction to ensure that identical trees result. See Section 12
for more details.
[8]Note that the expanding ring search yields the nearest server in
terms of hop count, but not necessarily in terms of the OSPF metric.
[9]This means that in MOSPF, just as in OSPF, the only kind of link
state advertisement that can be flooded between areas is the AS
external-link-LSA.
[10]A router indicates that it is a wild-card multicast receiver by
setting the appropriate flag in its router-LSA. See Section 14.6 for
details.
[11]This is not quite true. As we shall see, any inter-AS multicast
forwarders belonging to the backbone are designated as wild-card
multicast receivers. See Section 4.
[12]It is possible that through the operation of an inter-AS
multicast routing protocol, Router RT7 knows that it does not have
multicast connectivity to Network N15 (even though it has unicast
connectivity). In this case, RT7 would not advertise the external
link to N15 as being multicast capable.
[13]Synchronization of the IPMulticastForwarding interface parameter
is not enforced by the MOSPF protocol, since it is not included in
the contents of a MOSPF router's Hello packets.
[14]Actually, when multiple IP networks have been assigned to the
same physical network, the first thing that needs to be done is to
associate an IP network with the received Host Membership Report.
This is done in the same way that a receiving interface is
associated with a received multicast datagram; see Section 11.1.
[15]For this reason when a transit network has both MOSPF routers
and non-multicast OSPF routers attached, care should be taken to
ensure that a MOSPF router is elected Designated Router. This can be
accomplished through proper setting of the routers' configured
Router Priority.
[16]Note that just because these advertisements exist in the link
state database, it does not mean that the Group G members are
reachable. Reachability does not enter into the building of the
transit vertex list, in order to simplify the calculation. This is a
trade-off. As a result, some multicast datagrams may be forwarded
further than necessary, when the described Group G members actually
are unreachable.
[17]Since the Designated Router controls flooding on the network,
this is another reason to ensure that a MOSPF router is elected as
Designated Router.
[18]In other words, group-membership-LSAs will never be
retransmitted to non-multicast routers.
[19]This last step will not be necessary if the configuration
guidelines presented in Section 6.5 are followed.
[20]The TOS 0 routing table entry is examined regardless of the TOS
specified by the multicast datagram.
[21]It is assumed that a MOSPF router that wants to stop advertising
a route to an external destination will use the premature aging
procedure specified in Section 14.1 of [OSPF], rather than setting
the AS external-link-LSA's cost to LSInfinity.
[22]This preference ordering is used in Step 5c of Section 12.2.
[23]No attempt is made to match the links' two halves. See Step 5d.
[24]However, a summary-link-LSA is eligible for matching even if the
MC-bit in its Options field is clear.
[25]Costs may have both a Type 2 and a Type 1 component; the Type 2
component is always most significant.
[26]This case mirrors the SourceIntraArea candidate list
initialization in Section 12.2.1.
[27]This case mirrors the SourceInterArea1 candidate list
initialization in Section 12.2.2.
[28]This case mirrors the SourceInterArea2 candidate list
initialization in Section 12.2.3.
[29]Note that selecting the upstream node in this manner enforces
the inter-area routing architecture outlined in Section 3.1. Namely,
the multicast datagram is forwarded from the source area, over the
backbone and then into the non-backbone areas. This is similar to
the "hub and spoke" architecture for unicast forwarding described in
Section 3.2 of [OSPF].
[30]This procedure seems backwards. One would expect that the TOS X
datagram tree would be built first. However, the SPF calculation
must ensure that all routers participating in the forwarding of that
datagram, both TOS-capable and non-TOS-capable, build the same tree.
Since it is known that the non-TOS-capable routers will use the TOS
0 tree, the only safe way to use the TOS X tree is when you are
guaranteed that the non-TOS-capable routers will decline to forward
the datagram. This guarantee is clearly met when there are only
TOS-capable routers on the TOS 0 datagram tree.
[31]Indeed, there will also be those cases where the router, not
being on a particular datagram shortest-path tree, will never have
to calculate the particular tree, since the router will not receive
the datagram in the first place.
[32]Group-membership-LSAs are not processed by non-multicast routers
(see Section 10.2). Also, if the Designated Router was not running
the multicast extensions, multicast datagrams would not be forwarded
over the network because its network-LSA would have its MC-bit clear
(see Step 5a in Section 12.2).
A. Data Formats
This section documents the format of MOSPF protocol packets and link
state advertisements (LSAs). All changes and additions made to the
OSPF Version 2 data formats have been made in a backward-compatible
manner. In other words, multicast routers running MOSPF can
interoperate with (non-multicast) OSPF Version 2 routers when
forwarding regular (unicast) IP data traffic.
The MOSPF packet formats are the same as for OSPF Version 2
(described in Appendix A of [OSPF]). One additional option has been
added to the Options field that appears in OSPF Hello packets,
Database Description packets and all link state advertisements. This
new option indicates a router's/network's multicast capability, and
is documented in Section A.1. The presence of this new option is
ignored by all non-multicast routers.
To support MOSPF, one of OSPF's link state advertisements has been
modified, and a new link state advertisement has been added. The
format of the router-LSA has been modified (see Section A.2) to
include a new flag indicating whether the router is a wild-card
multicast receiver. A new link state advertisement, called the
group-membership-LSA, has been added to pinpoint multicast group
members in the link state database. This new advertisement is
neither flooded nor processed by non-multicast routers. The group-
membership-LSA is documented in Section A.3.
A.1 The Options field
The OSPF Options field is present in OSPF Hello packets, Database
Description packets and all link state advertisements. The Options
field enables OSPF routers to support (or not support) optional
capabilities, and to communicate their capability level to other
OSPF routers. Through this mechanism routers of differing
capabilities can be mixed within an OSPF routing domain.
When used in Hello packets, the Options field allows a router to
reject a neighbor because of a capability mismatch. Alternatively,
when capabilities are exchanged in Database Description packets a
router can choose not to forward certain LSA types to a neighbor
because of its reduced functionality. Lastly, listing capabilities
in LSAs allows routers to route traffic around reduced functionality
routers, by excluding them from parts of the routing table
calculation.
Three capabilities are currently defined. For each capability, the
effect of the capability's appearance (or lack of appearance) in
Hello packets, Database Description packets and link state
advertisements is specified below. For example, the
ExternalRoutingCapability (below called the E-bit) has meaning only
in OSPF Hello packets.
+---+---+---+---+---+---+---+---+
| * | * | * | * | * |MC | E | T |
+---+---+---+---+---+---+---+-+-+
The OSPF Options field
o T-bit. This describes the router's TOS capability. If the T-bit
is reset, then the router supports only a single TOS (TOS 0).
Such a router is also said to be incapable of TOS-routing. The
absence of the T-bit in a router links advertisement causes the
router to be skipped when building a non-zero TOS shortest-path
tree. In other words, routers incapable of TOS routing will be
avoided as much as possible when forwarding data traffic
requesting a non-zero TOS. The absence of the T-bit in a summary
link advertisement or an AS external link advertisement
indicates that the advertisement is describing a TOS 0 route
only (and not routes for non-zero TOS).
o E-bit. AS external link advertisements are not flooded
into/through OSPF stub areas. The E-bit ensures that all members
of a stub area agree on that area's configuration. The E-bit is
meaningful only in OSPF Hello packets. When the E-bit is reset
in the Hello packet sent out a particular interface, it means
that the router will neither send nor receive AS external link
state advertisements on that interface (in other words, the
interface connects to a stub area). Two routers will not become
neighbors unless they agree on the state of the E-bit.
o MC-bit. The MC-bit describes the multicast capability of the
various pieces of the OSPF routing domain. When calculating the
path of multicast datagrams, only those link state
advertisements having their MC-bit set are used. In addition, a
router uses the MC-bit in its Database Description packets to
tell adjacent neighbors whether the router will participate in
the flooding of the new group-membership-LSAs.
A.2 Router-LSA
An OSPF router originates a router-LSA into each of its attached
areas. The router-LSA describes the state and cost of the router's
interfaces to the area. The contents of the router-LSA are described
in detail in Section A.4.2 of [OSPF]. There are flags in the
router-LSA that indicate whether the router is either a) an area
border router or b) an AS boundary router or c) the endpoint of a
virtual link. One more flag has been added to the router-LSA for
MOSPF; it is called bit W below. This flag indicates whether the
router wishes to receive all multicast datagrams regardless of
destination (i.e., is a wild-card multicast receiver).
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| LS age | Options | 1 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Link State ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Advertising Router |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| LS sequence number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+