state retransmission lists.
(d) Install the new LSA in the link state database (replacing
the current database copy). This may cause the routing
table calculation to be scheduled. In addition, timestamp
the new LSA with the current time (i.e., the time it was
received). The flooding procedure cannot overwrite the
newly installed LSA until MinLSArrival seconds have elapsed.
The LSA installation process is discussed further in Section
13.2.
(e) Possibly acknowledge the receipt of the LSA by sending a
Link State Acknowledgment packet back out the receiving
interface. This is explained below in Section 13.5.
(f) If this new LSA indicates that it was originated by the
receiving router itself (i.e., is considered a self-
originated LSA), the router must take special action, either
updating the LSA or in some cases flushing it from the
routing domain. For a description of how self-originated
LSAs are detected and subsequently handled, see Section
13.4.
(6) Else, if there is an instance of the LSA on the sending
neighbor's Link state request list, an error has occurred in the
Database Exchange process. In this case, restart the Database
Exchange process by generating the neighbor event BadLSReq for
the sending neighbor and stop processing the Link State Update
packet.
(7) Else, if the received LSA is the same instance as the database
copy (i.e., neither one is more recent) the following two steps
should be performed:
(a) If the LSA is listed in the Link state retransmission list
for the receiving adjacency, the router itself is expecting
an acknowledgment for this LSA. The router should treat the
received LSA as an acknowledgment by removing the LSA from
the Link state retransmission list. This is termed an
"implied acknowledgment". Its occurrence should be noted
for later use by the acknowledgment process (Section 13.5).
(b) Possibly acknowledge the receipt of the LSA by sending a
Link State Acknowledgment packet back out the receiving
interface. This is explained below in Section 13.5.
(8) Else, the database copy is more recent. If the database copy
has LS age equal to MaxAge and LS sequence number equal to
MaxSequenceNumber, simply discard the received LSA without
acknowledging it. (In this case, the LSA's LS sequence number is
wrapping, and the MaxSequenceNumber LSA must be completely
flushed before any new LSA instance can be introduced).
Otherwise, send the database copy back to the sending neighbor,
encapsulated within a Link State Update Packet. The Link State
Update Packet should be unicast to the neighbor. In so doing, do
not put the database copy of the LSA on the neighbor's link
state retransmission list, and do not acknowledge the received
(less recent) LSA instance.
13.1. Determining which LSA is newer
When a router encounters two instances of an LSA, it must determine
which is more recent. This occurred above when comparing a received
LSA to its database copy. This comparison must also be done during
the Database Exchange procedure which occurs during adjacency bring-
up.
An LSA is identified by its LS type, Link State ID and Advertising
Router. For two instances of the same LSA, the LS sequence number,
LS age, and LS checksum fields are used to determine which instance
is more recent:
o The LSA having the newer LS sequence number is more recent.
See Section 12.1.6 for an explanation of the LS sequence number
space. If both instances have the same LS sequence number, then:
o If the two instances have different LS checksums, then the
instance having the larger LS checksum (when considered as a 16-
bit unsigned integer) is considered more recent.
o Else, if only one of the instances has its LS age field set
to MaxAge, the instance of age MaxAge is considered to be more
recent.
o Else, if the LS age fields of the two instances differ by
more than MaxAgeDiff, the instance having the smaller (younger)
LS age is considered to be more recent.
o Else, the two instances are considered to be identical.
13.2. Installing LSAs in the database
Installing a new LSA in the database, either as the result of
flooding or a newly self-originated LSA, may cause the OSPF routing
table structure to be recalculated. The contents of the new LSA
should be compared to the old instance, if present. If there is no
difference, there is no need to recalculate the routing table. When
comparing an LSA to its previous instance, the following are all
considered to be differences in contents:
o The LSA's Options field has changed.
o One of the LSA instances has LS age set to MaxAge, and
the other does not.
o The length field in the LSA header has changed.
o The body of the LSA (i.e., anything outside the 20-byte
LSA header) has changed. Note that this excludes changes in LS
Sequence Number and LS Checksum.
If the contents are different, the following pieces of the routing
table must be recalculated, depending on the new LSA's LS type field:
Router-LSAs and network-LSAs
The entire routing table must be recalculated, starting with the
shortest path calculations for each area (not just the area whose
link-state database has changed). The reason that the shortest
path calculation cannot be restricted to the single changed area
has to do with the fact that AS boundary routers may belong to
multiple areas. A change in the area currently providing the best
route may force the router to use an intra-area route provided by
a different area.[19]
Summary-LSAs
The best route to the destination described by the summary-LSA
must be recalculated (see Section 16.5). If this destination is
an AS boundary router, it may also be necessary to re-examine all
the AS-external-LSAs.
AS-external-LSAs
The best route to the destination described by the AS-external-LSA
must be recalculated (see Section 16.6).
Also, any old instance of the LSA must be removed from the
database when the new LSA is installed. This old instance must
also be removed from all neighbors' Link state retransmission
lists (see Section 10).
13.3. Next step in the flooding procedure
When a new (and more recent) LSA has been received, it must be
flooded out some set of the router's interfaces. This section
describes the second part of flooding procedure (the first part being
the processing that occurred in Section 13), namely, selecting the
outgoing interfaces and adding the LSA to the appropriate neighbors'
Link state retransmission lists. Also included in this part of the
flooding procedure is the maintenance of the neighbors' Link state
request lists.
This section is equally applicable to the flooding of an LSA that the
router itself has just originated (see Section 12.4).
For these LSAs, this section provides the entirety of the flooding
procedure (i.e., the processing of Section 13 is not performed,
since, for example, the LSA has not been received from a neighbor and
therefore does not need to be acknowledged).
Depending upon the LSA's LS type, the LSA can be flooded out only
certain interfaces. These interfaces, defined by the following, are
called the eligible interfaces:
AS-external-LSAs (LS Type = 5)
AS-external-LSAs are flooded throughout the entire AS, with the
exception of stub areas (see Section 3.6). The eligible
interfaces are all the router's interfaces, excluding virtual
links and those interfaces attaching to stub areas.
All other LS types
All other types are specific to a single area (Area A). The
eligible interfaces are all those interfaces attaching to the Area
A. If Area A is the backbone, this includes all the virtual
links.
Link state databases must remain synchronized over all adjacencies
associated with the above eligible interfaces. This is accomplished
by executing the following steps on each eligible interface. It
should be noted that this procedure may decide not to flood an LSA
out a particular interface, if there is a high probability that the
attached neighbors have already received the LSA. However, in these
cases the flooding procedure must be absolutely sure that the
neighbors eventually do receive the LSA, so the LSA is still added to
each adjacency's Link state retransmission list. For each eligible
interface:
(1) Each of the neighbors attached to this interface are
examined, to determine whether they must receive the new
LSA. The following steps are executed for each neighbor:
(a) If the neighbor is in a lesser state than Exchange, it
does not participate in flooding, and the next neighbor
should be examined.
(b) Else, if the adjacency is not yet full (neighbor state
is Exchange or Loading), examine the Link state request
list associated with this adjacency. If there is an
instance of the new LSA on the list, it indicates that
the neighboring router has an instance of the LSA
already. Compare the new LSA to the neighbor's copy:
o If the new LSA is less recent, then examine the next
neighbor.
o If the two copies are the same instance, then delete
the LSA from the Link state request list, and
examine the next neighbor.[20]
o Else, the new LSA is more recent. Delete the LSA
from the Link state request list.
(c) If the new LSA was received from this neighbor, examine
the next neighbor.
(d) At this point we are not positive that the neighbor has
an up-to-date instance of this new LSA. Add the new LSA
to the Link state retransmission list for the adjacency.
This ensures that the flooding procedure is reliable;
the LSA will be retransmitted at intervals until an
acknowledgment is seen from the neighbor.
(2) The router must now decide whether to flood the new LSA out
this interface. If in the previous step, the LSA was NOT
added to any of the Link state retransmission lists, there
is no need to flood the LSA out the interface and the next
interface should be examined.
(3) If the new LSA was received on this interface, and it was
received from either the Designated Router or the Backup
Designated Router, chances are that all the neighbors have
received the LSA already. Therefore, examine the next
interface.
(4) If the new LSA was received on this interface, and the
interface state is Backup (i.e., the router itself is the
Backup Designated Router), examine the next interface. The
Designated Router will do the flooding on this interface.
However, if the Designated Router fails the router (i.e.,
the Backup Designated Router) will end up retransmitting the
updates.
(5) If this step is reached, the LSA must be flooded out the
interface. Send a Link State Update packet (including the
new LSA as contents) out the interface. The 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).
On broadcast networks, the Link State Update packets are
multicast. The destination IP address specified for the
Link State Update Packet depends on the state of the
interface. If the interface state is DR or Backup, the
address AllSPFRouters should be used. Otherwise, the
address AllDRouters should be used.
On non-broadcast networks, separate Link State Update
packets must be sent, as unicasts, to each adjacent neighbor
(i.e., those in state Exchange or greater). The destination
IP addresses for these packets are the neighbors' IP
addresses.
13.4. Receiving self-originated LSAs
It is a common occurrence for a router to receive self-originated
LSAs via the flooding procedure. A self-originated LSA is detected
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.
However, if the received self-originated LSA is newer than the last
instance that the router actually originated, the router must take
special action. The reception of such an LSA indicates that there
are LSAs in the routing domain that were originated by the router
before the last time it was restarted. In most cases, the router
must then advance the LSA's LS sequence number one past the received
LS sequence number, and originate a new instance of the LSA.
It may be the case the router no longer wishes to originate the
received LSA. Possible examples include: 1) the LSA is a summary-LSA
or AS-external-LSA and the router no longer has an (advertisable)
route to the destination, 2) the LSA is a network-LSA but the router
is no longer Designated Router for the network or 3) the LSA is a
network-LSA whose Link State ID is one of the router's own IP
interface addresses but whose Advertising Router is not equal to the
router's own Router ID (this latter case should be rare, and it
indicates that the router's Router ID has changed since originating
the LSA). In all these cases, instead of updating the LSA, the LSA
should be flushed from the routing domain by incrementing the
received LSA's LS age to MaxAge and reflooding (see Section 14.1).
13.5. Sending Link State Acknowledgment packets
Each newly received LSA must be acknowledged. This is usually done
by sending Link State Acknowledgment packets. However,
acknowledgments can also be accomplished implicitly by sending Link
State Update packets (see step 7a of Section 13).
Many acknowledgments may be grouped together into a single Link State
Acknowledgment packet. Such a packet is sent back out the interface
which received the LSAs. The packet can be sent in one of two ways:
delayed and sent on an interval timer, or sent directly (as a
unicast) to a particular neighbor. The particular acknowledgment
strategy used depends on the circumstances surrounding the receipt of
the LSA.
Sending delayed acknowledgments accomplishes several things: 1) it
facilitates the packaging of multiple acknowledgments in a single
Link State Acknowledgment packet, 2) it enables a single Link State
Acknowledgment packet to indicate acknowledgments to several
neighbors at once (through multicasting) and 3) it randomizes the
Link State Acknowledgment packets sent by the various routers
attached to a common network. The fixed interval between a router's
delayed transmissions must be short (less than RxmtInterval) or
needless retransmissions will ensue.
Direct acknowledgments are sent to a particular neighbor in response
to the receipt of duplicate LSAs. These acknowledgments are sent as
unicasts, and are sent immediately when the duplicate is received.
The precise procedure for sending Link State Acknowledgment packets
is described in Table 19. The circumstances surrounding the receipt
of the LSA are listed in the left column. The acknowledgment action
then taken is listed in one of the two right columns. This action
depends on the state of the concerned interface; interfaces in state
Backup behave differently from interfaces in all other states.
Delayed acknowledgments must be delivered to all adjacent routers
associated with the interface. On broadcast networks, this is
accomplished by sending the delayed Link State Acknowledgment packets
as multicasts. The Destination IP address used depends 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).
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 (see
Section 13, step 4).
Table 19: Sending link state acknowledgments.
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 as
unicasts (directly to the physical address of the neighbor). They
are never sent as multicasts. 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 and 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 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.
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 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.
(1) 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.
(2) Call the vertex just added to the tree vertex V. Examine
the LSA 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-LSA, and bit V of the router-LSA (see
Section A.4.2) is set, set Area A's TransitCapability to
TRUE. In any case, each link described by the LSA gives the
cost to an adjacent vertex. For each described link, (say
it joins vertex V to vertex W):
(a) If this is a link to a stub network, examine the next
link in V's LSA. Links to stub networks will be
considered in the second stage of the shortest path
calculation.
(b) Otherwise, W is a transit vertex (router or transit
network). Look up the vertex W's LSA (router-LSA or
network-LSA) in Area A's link state database. If the
LSA 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 LSA.[23]
(c) If vertex W is already on the shortest-path tree,
examine the next link in the LSA.
(d) 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:
o Greater than the value that already appears for
vertex W on the candidate list, then examine the
next link.
o 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.
o 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).
(3) 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).
(4) 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 or AS
boundary router, a routing table entry is added whose
destination type is "router". The Options field found in
the associated router-LSA is copied into the routing table
entry's Optional capabilities field. Call the newly added
vertex Router X. If Router X is the endpoint of one of the
calculating router's virtual links, and the virtual link
uses Area A as 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
Router X, and the virtual neighbor's IP address is set to
Router X's interface address (contained in Router X's
router-LSA) that points back to the root of the shortest-
path tree; equivalently, this is the interface that points
back to Router X's parent vertex on the shortest-path tree
(similar to the calculation in Section 16.1.1).
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-LSA). 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' LSA.
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' LSA.
(5) 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-LSA is found in the link state database. Each stub
network link appearing in the LSA is then examined, and the following
steps are executed:
(1) 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 LSA.
(2) 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-LSA whose
Link State ID is smaller than V's Router ID, reset the Link
State Origin to V's router-LSA.
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-LSA.
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-LSAs 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 order 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 [Ref1].
16.1.1. The next hop calculation
This section explains how to calculate the current set of next hops
to use for a destination. Each next hop consists of the outgoing
interface to use in forwarding packets to the destination together
with the IP address of the next hop router (if any). The next hop
calculation is invoked each time a shorter path to the destination is
discovered. This can happen in either stage of the shortest-path
tree calculation (see Section 16.1). In stage 1 of the shortest-path
tree calculation a shorter path is found as the destination is added
to the candidate list, or when the destination's entry on the
candidate list is modified (Step 2d of Stage 1). In stage 2 a
shorter path is discovered each time the destination's routing table
entry is modified (Step 2 of Stage 2).
The set of next hops to use for the destination may be recalculated
several times during the shortest-path tree calculation, as shorter
and shorter paths are discovered. In the end, the destination's
routing table entry will always reflect the next hops resulting from
the absolute shortest path(s).
Input to the next hop calculation is a) the destination and b) its
parent in the current shortest path between the root (the calculating
router) and the destination. The parent is always a transit vertex
(i.e., always a router or a transit network).
If there is at least one intervening router in the current shortest
path between the destination and the root, the destination simply
inherits the set of next hops from the parent. Otherwise, there are
two cases. In the first case, the parent vertex is the root (the
calculating router itself). This means that the destination is
either a directly connected network or directly connected router.
The outgoing interface in this case is simply the OSPF interface
connecting to the destination network/router. If the destination is a
router which connects to the calculating router via a Point-to-
MultiPoint network, the destination's next hop IP address(es) can be
determined by examining the destination's router-LSA: each link
pointing back to the calculating router and having a Link Data field
belonging to the Point-to-MultiPoint network provides an IP address
of the next hop router. If the destination is a directly connected
network, or a router which connects to the calculating router via a
point-to-point interface, no next hop IP address is required. If the
destination is a router connected to the calculating router via a
virtual link, the setting of the next hop should be deferred until
the calculation in Section 16.3.
In the second case, the parent vertex is a network that directly
connects the calculating router to the destination router. The list
of next hops is then determined by examining the destination's
router-LSA. For each link in the router-LSA that points back to the
parent network, the link's Link Data field provides the IP address of
a next hop router. The outgoing interface to use can then be derived
from the next hop IP address (or it can be inherited from the parent
network).
16.2. Calculating the inter-area routes
The inter-area routes are calculated by examining summary-LSAs. If
the router has active attachments to multiple areas, only backbone
summary-LSAs are examined. Routers attached to a single area examine
that area's summary-LSAs. In either case, the summary-LSAs examined
below are all part of a single area's link state database (call it
Area A).
Summary-LSAs are originated by the area border routers. Each
summary-LSA in Area A is considered in turn. Remember that the
destination described by a summary-LSA is either a network (Type 3
summary-LSAs) or an AS boundary router (Type 4 summary-LSAs). For
each summary-LSA:
(1) If the cost specified by the LSA is LSInfinity, or if the
LSA's LS age is equal to MaxAge, then examine the the next
LSA.
(2) If the LSA was originated by the calculating router itself,
examine the next LSA.
(3) If it is a Type 3 summary-LSA, and the collection of
destinations described by the summary-LSA equals one of the
router's configured area address ranges (see Section 3.5),
and the particular area address range is active, then the
summary-LSA should be ignored. "Active" means that there
are one or more reachable (by intra-area paths) networks
contained in the area range.
(4) Else, call the destination described by the LSA N (for Type
3 summary-LSAs, N's address is obtained by masking the LSA's
Link State ID with the network/subnet mask contained in the
body of the LSA), and the area border originating the LSA
BR. Look up the routing table entry for BR having Area A as
its associated area. If no such entry exists for router BR
(i.e., BR is unreachable in Area A), do nothing with this
LSA and consider the next in the list. Else, this LSA
describes an inter-area path to destination N, whose cost is
the distance to BR plus the cost specified in the LSA. Call
the cost of this inter-area path IAC.
(5) Next, look up the routing table entry for the destination N.
(If N is an AS boundary router, look up the "router" routing
table entry associated with Area A). If no entry exists for
N or if the entry's path type is "type 1 external" or "type
2 external", then install the inter-area path to N, with
associated area Area A, cost IAC, next hop equal to the list
of next hops to router BR, and Advertising router equal to
BR.
(6) Else, if the paths present in the table are intra-area
paths, do nothing with the LSA (intra-area paths are always
preferred).
(7) Else, the paths present in the routing table are also
inter-area paths. Install the new path through BR if it is
cheaper, overriding the paths in the routing table.
Otherwise, if the new path is the same cost, add it to the
list of paths that appear in the routing table entry.
16.3. Examining transit areas' summary-LSAs
This step is only performed by area border routers attached to one or
more non-backbone areas that are capable of carrying transit traffic
(i.e., "transit areas", or those areas whose TransitCapability