OSPF Operation

The main operation of the OSPF protocol occurs in the following consecutive stages and leads to the convergence of the internetwork:

1. Compiling the LSDB.

2. Calculating the Shortest Path First (SPF) Tree.

3. Creating the routing table entries.

Formation of the LSDB Using Link State Advertisements

The LSDB is a database of all OSPF router LSAs, summary LSAs, and external route LSAs. The LSDB is compiled by an ongoing exchange of LSAs between neighboring routers so that each router is synchronized with its neighbor. When the AS has converged, all routers have the appropriate entries in their LSDB.

To create the LSDB, each OSPF router must receive a valid LSA from each other router in the AS. This is performed through a procedure called flooding. Each router initially sends out an LSA which contains its own configuration. As it receives LSAs from other routers, it propagates those LSAs to its neighbor routers.

In this way, an LSA from a given router is flooded across the AS so that each other router contains that router's LSA. While it appears that the flooding of LSAs across the AS causes a large amount of network traffic, OSPF is very efficient in the propagation of LSA information. Figure 3.11 shows a simple OSPF AS, the flooding of LSAs between neighboring routers, and the LSDB.

The exact details of the synchronization of the LSDB between neighboring routers are discussed in the section on creating adjacencies.

Figure 3.11 OSPF Link State Database (LSDB)

You can view the current OSPF link state database by right-clicking the OSPF routing protocol and clicking Show Link State Database in the Routing and Remote Access snap-in.

Router ID

To keep track of LSAs in the LSDB, each router is assigned a Router ID, a 32-bit dotted decimal number that is unique to the AS. The Router ID identifies the router in the AS, not the IP address of one of the router's interfaces. The Router ID is not used as a destination IP address for sending information to the router. It is a common industry convention to use the largest or smallest IP address assigned to the router as the Router ID. Because IP addresses are unique, this convention ensures that the OSPF Router IDs are also unique.

Calculating the SPF Tree Using Dijkstra's Algorithm

Once the LSDB is compiled, each OSPF router performs a least cost path calculation called the Dijkstra algorithm on the information in the LSDB and creates a tree of shortest paths to each other router and network with themselves as the root. This tree is known as the SPF Tree and contains a single, least cost path to each router and network in the AS. Because the least cost path calculation is performed by each router with itself as the root of the tree, the SPF tree is different for each router in the AS.

The Dijkstra algorithm is from a branch of mathematics called graph theory and is an efficient method of calculating a set of least cost paths relative to a source node.

To Calculate the SPF Tree Using the Dijkstra Algorithm

The result of the Dijkstra algorithm is the set SPF{}, a cost sorted list of least cost paths containing the path (the series of nodes and links) and its accumulated cost from the source node S.

1. Define the set E{} to be the set of nodes (routers) that have been evaluated.

2. Define the set R{} to be the set of nodes (routers) that are remaining (have not been evaluated).

3. Define the set O{} to be a cost-sorted list of ordered paths between nodes. An ordered path can consist of multiple nodes connected together in a multi-hop configuration (they do not have to be neighboring).

4. Define the set SPF{} to be a cost-sorted list of least cost paths containing the path and its accumulated cost.

5. Initialize the set E{} to contain the source node S and the set R{} to contain all other nodes. Initialize the set O{} to be the cost-sorted list of directly connected paths from S. Initialize the set SPF{} to be the empty set.

6. If O{} is empty or the first path in O{} has an infinite metric, mark all the nodes in R as unreachable and terminate the algorithm.

7. From the set O{}, examine P, the shortest ordered path in O{}. Remove P from O{}. Let V be the last node on the ordered path of P.
   If V is already a member of E{}, return to step 6.
   – Or –
   If P is the shortest path to V, move V from R{} to E{}. Add a member to the set SPF{} consisting of P and its accumulated cost from S.

8. Build a new set of paths by concatenating P and each of the links adjacent to V. The cost of these paths is the sum of the cost of P and the metric of the link appended to P. Insert the new links in the set O{} and sort by cost. Return to step 6.

Calculating the Routing Table Entries from the SPF Tree

The OSPF routing table entries are created from the SPF tree, and a single entry for each network in the AS is produced. The metric for the routing table entry is the OSPF-calculated cost, not a hop count.

To calculate the IP routing table entries from the SPF Tree, the resulting set SPF{} is analyzed. The result of the analysis is a series of OSPF routes containing the IP destination (the network ID) and its network mask (subnet mask), the forwarding IP address of the appropriate neighboring router, the interface over which the neighboring router is reachable, and the OSPF-calculated cost to the network. The OSPF routes are added to the IP routing table.

Example of OSPF Operation

The following examples illustrate how an OSPF internetwork compiles the LSDB, performs the least cost analysis, and creates routing table entries. This example is deliberately simplified to help you gain an understanding of the basic principles of OSPF convergence.

Compiling the LSDB

Consider the simple AS in Figure 3.12. At each router interface, a unitless cost metric is assigned as a reflection of the preference of using that interface. These cost values can be a reflection of bandwidth, delay, or reliability factors and are assigned by the network administrator.

Figure 3.12 AS with Link State Database Information

After convergence, when each router has an LSA from each other router in the AS, they each contain the LSDB shown in Table 3.1.

Table 3.1 Link State Database

Calculating the SPF Tree

The next step is to apply Dijkstra's algorithm to our sample OSPF AS. Figure 3.13 illustrates the resulting SPF Tree calculation as performed by router R4. With R4 as the root, the SPF Tree calculation determines the series of connected routers and networks that represent the least cost path to each router and to each network.

Figure 3.13 SPF Tree

Creating Routing Table Entries

The routing table is created from the results of the SPF Tree as shown in Figure 3.14.

Figure 3.14 Routing Table Entries

Note

A large OSPF network might require a short but large burst of bandwidth as LSAs are exchanged. Once the LSAs are exchanged a large amount of memory is required to hold the LSDB before convergence. Running the SPF algorithm requires high CPU utilization. Networks with frequently appearing and disappearing links might cause performance issues on any router because of the three-step LSA generation, holding the LSDB, and running the SPF process. The overhead and performance issues of OSPF can be minimized by dividing the OSPF AS into areas. For more information, see "OSPF Areas" later in this chapter.