14. Aging The Link State Database
Action taken in state
Circumstances Backup All other states
LSA has No acknowledgment No acknowledgment been flooded back sent. sent. out receiving in- terface (see Sec- tion 13, step 5b).
LSA is Delayed acknowledg- Delayed ack- more recent than ment sent if adver- nowledgment sent. database copy, but tisement received was not flooded from Designated back out receiving Router, otherwise interface do nothing
LSA is a Delayed acknowledg- No acknowledgment duplicate, and was ment sent if adver- sent. treated as an im- tisement received plied acknowledg- from Designated ment (see Section Router, otherwise 13, step 7a). do nothing
LSA is a Direct acknowledg- Direct acknowledg- duplicate, and was ment sent. ment sent. not treated as an implied ack- nowledgment.
LSA's LS Direct acknowledg- Direct acknowledg- age is equal to ment sent. ment sent. MaxAge, and there is no current instance of the LSA in the link state database, and none of router's neighbors are in states Exchange
or Loading (see Section 13, step 4).
Table 19: Sending link state acknowledgements.
on the state of the interface. If the interface state is DR or
Backup, the destination AllSPFRouters is used. In all other
states, the destination AllDRouters is used. On non-broadcast
networks, delayed Link State Acknowledgment packets must be
unicast separately over each adjacency (i.e., neighbor whose
state is >= Exchange).
The reasoning behind sending the above packets as multicasts is
best explained by an example. Consider the network
configuration depicted in Figure 15. Suppose RT4 has been
elected as Designated Router, and RT3 as Backup Designated
Router for the network N3. When Router RT4 floods a new LSA to
Network N3, it is received by routers RT1, RT2, and RT3. These
routers will not flood the LSA back onto net N3, but they still
must ensure that their link-state databases remain synchronized
with their adjacent neighbors. So RT1, RT2, and RT4 are waiting
to see an acknowledgment from RT3. Likewise, RT4 and RT3 are
both waiting to see acknowledgments from RT1 and RT2. This is
best achieved by sending the acknowledgments as multicasts.
The reason that the acknowledgment logic for Backup DRs is
slightly different is because they perform differently during
the flooding of LSAs (see Section 13.3, step 4).
13.6. Retransmitting LSAs
LSAs flooded out an adjacency are placed on the adjacency's Link
state retransmission list. In order to ensure that flooding is
reliable, these LSAs are retransmitted until they are
acknowledged. The length of time between retransmissions is a
configurable per-interface value, RxmtInterval. If this is set
too low for an interface, needless retransmissions will ensue.
If the value is set too high, the speed of the flooding, in the
face of lost packets, may be affected.
Several retransmitted LSAs may fit into a single Link State
Update packet. When LSAs are to be retransmitted, only the
number fitting in a single Link State Update packet should be
sent. Another packet of retransmissions can be sent whenever
some of the LSAs are acknowledged, or on the next firing of the
retransmission timer.
Link State Update Packets carrying retransmissions are always
sent directly to the neighbor. On multi-access networks, this
means that retransmissions are sent directly to the neighbor's
IP address. Each LSA's LS age must be incremented by
InfTransDelay (which must be > 0) when it is copied into the
outgoing Link State Update packet (until the LS age field
reaches the maximum value of MaxAge).
If an adjacent router goes down, retransmissions may occur until
the adjacency is destroyed by OSPF's Hello Protocol. When the
adjacency is destroyed, the Link state retransmission list is
cleared.
13.7. Receiving link state acknowledgments
Many consistency checks have been made on a received Link State
Acknowledgment packet before it is handed to the flooding
procedure. In particular, it has been associated with a
particular neighbor. If this neighbor is in a lesser state than
Exchange, the Link State Acknowledgment packet is discarded.
Otherwise, for each acknowledgment in the Link State
Acknowledgment packet, the following steps are performed:
o Does the LSA acknowledged have an instance on the Link state
retransmission list for the neighbor? If not, examine the
next acknowledgment. Otherwise:
o If the acknowledgment is for the same instance that is
contained on the list, remove the item from the list and
examine the next acknowledgment. Otherwise:
o Log the questionable acknowledgment, and examine the next
one.
14. Aging The Link State Database
Each LSA has an LS age field. The LS age is expressed in seconds.
An LSA's LS age field is incremented while it is contained in a
router's database. Also, when copied into a Link State Update
Packet for flooding out a particular interface, the LSA's LS age is
incremented by InfTransDelay.
An LSA's LS age is never incremented past the value MaxAge. LSAs
having age MaxAge are not used in the routing table calculation. As
a router ages its link state database, an LSA's LS age may reach
MaxAge.[21] At this time, the router must attempt to flush the LSA
from the routing domain. This is done simply by reflooding the
MaxAge LSA just as if it was a newly originated LSA (see Section
13.3).
When creating a Database summary list for a newly forming adjacency,
any MaxAge LSAs present in the link state database are added to the
neighbor's Link state retransmission list instead of the neighbor's
Database summary list. See Section 10.3 for more details.
A MaxAge LSA must be removed immediately from the router's link
state database as soon as both a) it is no longer contained on any
neighbor Link state retransmission lists and b) none of the router's
neighbors are in states Exchange or Loading.
When, in the process of aging the link state database, an LSA's LS
age hits a multiple of CheckAge, its LS checksum should be verified.
If the LS checksum is incorrect, a program or memory error has been
detected, and at the very least the router itself should be
restarted.
14.1. Premature aging of LSAs
An LSA can be flushed from the routing domain by setting its LS
age to MaxAge, while leaving its LS sequence number alone, and
then reflooding the LSA. This procedure follows the same course
as flushing an LSA whose LS age has naturally reached the value
MaxAge (see Section 14). In particular, the MaxAge LSA is
removed from the router's link state database as soon as a) it
is no longer contained on any neighbor Link state retransmission
lists and b) none of the router's neighbors are in states
Exchange or Loading. We call the setting of an LSA's LS age to
MaxAge "premature aging".
Premature aging is used when it is time for a self-originated
LSA's sequence number field to wrap. At this point, the current
LSA instance (having LS sequence number MaxSequenceNumber) must
be prematurely aged and flushed from the routing domain before a
new instance with sequence number equal to InitialSequenceNumber
can be originated. See Section 12.1.6 for more information.
Premature aging can also be used when, for example, one of the
router's previously advertised external routes is no longer
reachable. In this circumstance, the router can flush its AS-
external-LSA from the routing domain via premature aging. This
procedure is preferable to the alternative, which is to
originate a new LSA for the destination specifying a metric of
LSInfinity. Premature aging is also be used when unexpectedly
receiving self-originated LSAs during the flooding procedure
(see Section 13.4).
A router may only prematurely age its own self-originated LSAs.
The router may not prematurely age LSAs that have been
originated by other routers. An LSA is considered self-
originated when either 1) the LSA's Advertising Router is equal
to the router's own Router ID or 2) the LSA is a network-LSA and
its Link State ID is equal to one of the router's own IP
interface addresses.
15. Virtual Links
The single backbone area (Area ID = 0.0.0.0) cannot be disconnected,
or some areas of the Autonomous System will become unreachable. To
establish/maintain connectivity of the backbone, virtual links can
be configured through non-backbone areas. Virtual links serve to
connect physically separate components of the backbone. The two
endpoints of a virtual link are area border routers. The virtual
link must be configured in both routers. The configuration
information in each router consists of the other virtual endpoint
(the other area border router), and the non-backbone area the two
routers have in common (called the Transit area). Virtual links
cannot be configured through stub areas (see Section 3.6).
The virtual link is treated as if it were an unnumbered point-to-
point network belonging to the backbone and joining the two area
border routers. An attempt is made to establish an adjacency over
the virtual link. When this adjacency is established, the virtual
link will be included in backbone router-LSAs, and OSPF packets
pertaining to the backbone area will flow over the adjacency. Such
an adjacency has been referred to in this document as a "virtual
adjacency".
In each endpoint router, the cost and viability of the virtual link
is discovered by examining the routing table entry for the other
endpoint router. (The entry's associated area must be the
configured Transit area). This is called the virtual link's
corresponding routing table entry. The InterfaceUp event occurs for
a virtual link when its corresponding routing table entry becomes
reachable. Conversely, the InterfaceDown event occurs when its
routing table entry becomes unreachable. In other words, the
virtual link's viability is determined by the existence of an
intra-area path, through the Transit area, between the two
endpoints. Note that a virtual link whose underlying path has cost
greater than hexadecimal 0xffff (the maximum size of an interface
cost in a router-LSA) should be considered inoperational (i.e.,
treated the same as if the path did not exist).
The other details concerning virtual links are as follows:
o AS-external-LSAs are NEVER flooded over virtual adjacencies.
This would be duplication of effort, since the same AS-
external-LSAs are already flooded throughout the virtual link's
Transit area. For this same reason, AS-external-LSAs are not
summarized over virtual adjacencies during the Database Exchange
process.
o The cost of a virtual link is NOT configured. It is defined to
be the cost of the intra-area path between the two defining area
border routers. This cost appears in the virtual link's
corresponding routing table entry. When the cost of a virtual
link changes, a new router-LSA should be originated for the
backbone area.
o Just as the virtual link's cost and viability are determined by
the routing table build process (through construction of the
routing table entry for the other endpoint), so are the IP
interface address for the virtual interface and the virtual
neighbor's IP address. These are used when sending OSPF
protocol packets over the virtual link. Note that when one (or
both) of the virtual link endpoints connect to the Transit area
via an unnumbered point-to-point link, it may be impossible to
calculate either the virtual interface's IP address and/or the
virtual neighbor's IP address, thereby causing the virtual link
to fail.
o In each endpoint's router-LSA for the backbone, the virtual link
is represented as a Type 4 link whose Link ID is set to the
virtual neighbor's OSPF Router ID and whose Link Data is set to
the virtual interface's IP address. See Section 12.4.1 for more
information.
o A non-backbone area can carry transit data traffic (i.e., is
considered a "transit area") if and only if it serves as the
Transit area for one or more fully adjacent virtual links (see
TransitCapability in Sections 6 and 16.1). Such an area requires
special treatment when summarizing backbone networks into it
(see Section 12.4.3), and during the routing calculation (see
Section 16.3).
o The time between link state retransmissions, RxmtInterval, is
configured for a virtual link. This should be well over the
expected round-trip delay between the two routers. This may be
hard to estimate for a virtual link; it is better to err on the
side of making it too large.
16. Calculation of the routing table
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-LSA originated by a certain router).
This access is performed by the lookup function discussed in Section
12.2. The lookup process may return an LSA whose LS age is equal to
MaxAge. Such an LSA 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:
(1) 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.
(2) 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.
(3) The inter-area routes are calculated, through examination of
summary-LSAs. If the router is attached to multiple areas
(i.e., it is an area border router), only backbone summary-LSAs
are examined.
(4) 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-LSAs are examined to see
whether better paths exist using the transit areas than were
found in Steps 2-3 above.
(5) Routes to external destinations are calculated, through
examination of AS-external-LSAs. The locations of the AS
boundary routers (which originate the AS-external-LSAs) have
been determined in steps 2-4.
Steps 2-5 are explained in further detail below.
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-LSAs (see Section 12.4). See
Section 16.7 for a complete list of the OSPF protocol actions
resulting from routing table changes.
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.[22] 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 which together with the vertex type (router
or network) uniquely identifies the vertex. For router
vertices the Vertex ID is the router's OSPF Router ID. For
network vertices, it is the IP address of the network's
Designated Router.
An LSA
Each transit vertex has an associated LSA. For router
vertices, this is a router-LSA. For transit networks, this
is a network-LSA (which is actually originated by the
network's Designated Router). In any case, the LSA'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 broadcast,
Point-to-MultiPoint and NBMA 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-LSAs and
network-LSAs). 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