This section details the OSPF routing table calculation. Using its
attached areas' link state databases as input, a router runs the
following algorithm, building its routing table step by step. At
each step, the router must access individual pieces of the link
state databases (e.g., a router links advertisement originated by a
certain router). This access is performed by the lookup function
discussed in Section 12.2. The lookup process may return a link
state advertisement whose LS age is equal to MaxAge. Such an
advertisement should not be used in the routing table calculation,
and is treated just as if the lookup process had failed.
The OSPF routing table's organization is explained in Section 11.
Two examples of the routing table build process are presented in
Sections 11.2 and 11.3. This process can be broken into the
following steps:
The present routing table is invalidated. The routing table is
built again from scratch. The old routing table is saved so
that changes in routing table entries can be identified.
The intra-area routes are calculated by building the shortest-
path tree for each attached area. In particular, all routing
table entries whose Destination Type is "area border router" are
calculated in this step. This step is described in two parts.
At first the tree is constructed by only considering those links
between routers and transit networks. Then the stub networks
are incorporated into the tree. During the area's shortest-path
tree calculation, the area's TransitCapability is also
calculated for later use in Step 4.
The inter-area routes are calculated, through examination of
summary link advertisements. If the router is attached to
multiple areas (i.e., it is an area border router), only
backbone summary link advertisements are examined.
In area border routers connecting to one or more transit areas
(i.e, non-backbone areas whose TransitCapability is found to be
TRUE), the transit areas' summary link advertisements are
examined to see whether better paths exist using the transit
areas than were found in Steps 2-3 above.
Routes to external destinations are calculated, through
examination of AS external link advertisements. The locations
of the AS boundary routers (which originate the AS external link
advertisements) have been determined in steps 2-4.
Steps 2-5 are explained in further detail below. The explanations
describe the calculations for TOS 0 only. It may also be necessary
to perform each step (separately) for each of the non-zero TOS
values.[20] For more information concerning the building of non-zero
TOS routes see Section 16.9.
Changes made to routing table entries as a result of these
calculations can cause the OSPF protocol to take further actions.
For example, a change to an intra-area route will cause an area
border router to originate new summary link advertisements (see
Section 12.4). See Section 16.7 for a complete list of the OSPF
protocol actions resulting from routing table changes.