16.1. Calculating the shortest-path tree for an area

16.1. Calculating the shortest-path tree for an area

This calculation yields the set of intra-area routes associated
with an area (called hereafter Area A). A router calculates the
shortest-path tree using itself as the root.[21] The formation
of the shortest path tree is done here in two stages. In the
first stage, only links between routers and transit networks are
considered. Using the Dijkstra algorithm, a tree is formed from
this subset of the link state database. In the second stage,
leaves are added to the tree by considering the links to stub
networks.

The procedure will be explained using the graph terminology that
was introduced in Section 2. The area's link state database is
represented as a directed graph. The graph's vertices are
routers, transit networks and stub networks. The first stage of
the procedure concerns only the transit vertices (routers and
transit networks) and their connecting links. Throughout the
shortest path calculation, the following data is also associated
with each transit vertex:

Vertex (node) ID

A 32-bit number uniquely identifying the vertex. For router
vertices this is the router's OSPF Router ID. For network
vertices, this is the IP address of the network's Designated
Router.

A link state advertisement

Each transit vertex has an associated link state
advertisement. For router vertices, this is a router links
advertisement. For transit networks, this is a network
links advertisement (which is actually originated by the
network's Designated Router). In any case, the
advertisement's Link State ID is always equal to the above
Vertex ID.

List of next hops

The list of next hops for the current set of shortest paths
from the root to this vertex. There can be multiple
shortest paths due to the equal-cost multipath capability.
Each next hop indicates the outgoing router interface to use
when forwarding traffic to the destination. On multi-access
networks, the next hop also includes the IP address of the
next router (if any) in the path towards the destination.

Distance from root

The link state cost of the current set of shortest paths
from the root to the vertex. The link state cost of a path
is calculated as the sum of the costs of the path's
constituent links (as advertised in router links and network
links advertisements). One path is said to be "shorter"
than another if it has a smaller link state cost.

The first stage of the procedure (i.e., the Dijkstra algorithm)
can now be summarized as follows. At each iteration of the
algorithm, there is a list of candidate vertices. Paths from
the root to these vertices have been found, but not necessarily
the shortest ones. However, the paths to the candidate vertex
that is closest to the root are guaranteed to be shortest; this
vertex is added to the shortest-path tree, removed from the
candidate list, and its adjacent vertices are examined for
possible addition to/modification of the candidate list. The
algorithm then iterates again. It terminates when the candidate
list becomes empty.

The following steps describe the algorithm in detail. Remember
that we are computing the shortest path tree for Area A. All
references to link state database lookup below are from Area A's
database.

Initialize the algorithm's data structures. Clear the list
of candidate vertices. Initialize the shortest-path tree to
only the root (which is the router doing the calculation).
Set Area A's TransitCapability to FALSE.

Call the vertex just added to the tree vertex V. Examine
the link state advertisement associated with vertex V. This
is a lookup in the Area A's link state database based on the
Vertex ID. If this is a router links advertisement, and bit
V of the router links advertisement (see Section A.4.2) is
set, set Area A's TransitCapability to TRUE. In any case,
each link described by the advertisement gives the cost to
an adjacent vertex. For each described link, (say it joins
vertex V to vertex W):

If this is a link to a stub network, examine the next
link in V's advertisement. Links to stub networks will
be considered in the second stage of the shortest path
calculation.

Otherwise, W is a transit vertex (router or transit
network). Look up the vertex W's link state
advertisement (router links or network links) in Area
A's link state database. If the advertisement does not
exist, or its LS age is equal to MaxAge, or it does not
have a link back to vertex V, examine the next link in
V's advertisement.[22]

If vertex W is already on the shortest-path tree,
examine the next link in the advertisement.

Calculate the link state cost D of the resulting path
from the root to vertex W. D is equal to the sum of the
link state cost of the (already calculated) shortest
path to vertex V and the advertised cost of the link
between vertices V and W. If D is:

Greater than the value that already appears for
vertex W on the candidate list, then examine the
next link.

Equal to the value that appears for vertex W on the
candidate list, calculate the set of next hops that
result from using the advertised link. Input to
this calculation is the destination (W), and its
parent (V). This calculation is shown in Section
16.1.1. This set of hops should be added to the
next hop values that appear for W on the candidate
list.

Less than the value that appears for vertex W on the
candidate list, or if W does not yet appear on the
candidate list, then set the entry for W on the
candidate list to indicate a distance of D from the
root. Also calculate the list of next hops that
result from using the advertised link, setting the
next hop values for W accordingly. The next hop
calculation is described in Section 16.1.1; it takes
as input the destination (W) and its parent (V).

If at this step the candidate list is empty, the shortest-
path tree (of transit vertices) has been completely built
and this stage of the procedure terminates. Otherwise,
choose the vertex belonging to the candidate list that is
closest to the root, and add it to the shortest-path tree
(removing it from the candidate list in the process). Note
that when there is a choice of vertices closest to the root,
network vertices must be chosen before router vertices in
order to necessarily find all equal-cost paths. This is
consistent with the tie-breakers that were introduced in the
modified Dijkstra algorithm used by OSPF's Multicast routing
extensions (MOSPF).

Possibly modify the routing table. For those routing table
entries modified, the associated area will be set to Area A,
the path type will be set to intra-area, and the cost will
be set to the newly discovered shortest path's calculated
distance.

If the newly added vertex is an area border router (call it
ABR), a routing table entry is added whose destination type
is "area border router". The Options field found in the
associated router links advertisement is copied into the
routing table entry's Optional capabilities field. If in
addition ABR is the endpoint of one of the calculating
router's configured virtual links that uses Area A as its
Transit area: the virtual link is declared up, the IP
address of the virtual interface is set to the IP address of
the outgoing interface calculated above for ABR, and the
virtual neighbor's IP address is set to the ABR interface
address (contained in ABR's router links advertisement) that
points back to the root of the shortest-path tree;
equivalently, this is the interface that points back to
ABR's parent vertex on the shortest-path tree (similar to
the calculation in Section 16.1.1).

If the newly added vertex is an AS boundary router, the
routing table entry of type "AS boundary router" for the
destination is located. Since routers can belong to more
than one area, it is possible that several sets of intra-
area paths exist to the AS boundary router, each set using a
different area. However, the AS boundary router's routing
table entry must indicate a set of paths which utilize a
single area. The area leading to the routing table entry is
selected as follows: The area providing the shortest path is
always chosen; if more than one area provides paths with the
same minimum cost, the area with the largest OSPF Area ID
(when considered as an unsigned 32-bit integer) is chosen.
Note that whenever an AS boundary router's routing table
entry is added/modified, the Options found in the associated
router links advertisement is copied into the routing table
entry's Optional capabilities field.

If the newly added vertex is a transit network, the routing
table entry for the network is located. The entry's
Destination ID is the IP network number, which can be
obtained by masking the Vertex ID (Link State ID) with its
associated subnet mask (found in the body of the associated
network links advertisement). If the routing table entry
already exists (i.e., there is already an intra-area route
to the destination installed in the routing table), multiple
vertices have mapped to the same IP network. For example,
this can occur when a new Designated Router is being
established. In this case, the current routing table entry
should be overwritten if and only if the newly found path is
just as short and the current routing table entry's Link
State Origin has a smaller Link State ID than the newly
added vertex' link state advertisement.

If there is no routing table entry for the network (the
usual case), a routing table entry for the IP network should
be added. The routing table entry's Link State Origin
should be set to the newly added vertex' link state
advertisement.

Iterate the algorithm by returning to Step 2.

The stub networks are added to the tree in the procedure's
second stage. In this stage, all router vertices are again
examined. Those that have been determined to be unreachable in
the above first phase are discarded. For each reachable router
vertex (call it V), the associated router links advertisement is
found in the link state database. Each stub network link
appearing in the advertisement is then examined, and the
following steps are executed:

Calculate the distance D of stub network from the root. D
is equal to the distance from the root to the router vertex
(calculated in stage 1), plus the stub network link's
advertised cost. Compare this distance to the current best
cost to the stub network. This is done by looking up the
stub network's current routing table entry. If the
calculated distance D is larger, go on to examine the next
stub network link in the advertisement.

If this step is reached, the stub network's routing table
entry must be updated. Calculate the set of next hops that
would result from using the stub network link. This
calculation is shown in Section 16.1.1; input to this
calculation is the destination (the stub network) and the
parent vertex (the router vertex). If the distance D is the
same as the current routing table cost, simply add this set
of next hops to the routing table entry's list of next hops.
In this case, the routing table already has a Link State
Origin. If this Link State Origin is a router links
advertisement whose Link State ID is smaller than V's Router
ID, reset the Link State Origin to V's router links
advertisement.

Otherwise D is smaller than the routing table cost.
Overwrite the current routing table entry by setting the
routing table entry's cost to D, and by setting the entry's
list of next hops to the newly calculated set. Set the
routing table entry's Link State Origin to V's router links
advertisement. Then go on to examine the next stub network
link.

For all routing table entries added/modified in the second
stage, the associated area will be set to Area A and the path
type will be set to intra-area. When the list of reachable
router links is exhausted, the second stage is completed. At
this time, all intra-area routes associated with Area A have
been determined.

The specification does not require that the above two stage
method be used to calculate the shortest path tree. However, if
another algorithm is used, an identical tree must be produced.
For this reason, it is important to note that links between
transit vertices must be bidirectional in ordered to be included
in the above tree. It should also be mentioned that more
efficient algorithms exist for calculating the tree; for
example, the incremental SPF algorithm described in [BBN].