The Topology Database
The topology database is the router’s view of the network within the area. It includes every OSPF router within the area and all the connected networks. This database is indeed a routing table, but a routing table for which no path decisions have been made; it is at present a topology database.
The topology database is updated by the LSAs. Each router within the area has exactly the same topology database. All routers must have the same vision of the network; otherwise, confusion, routing loops, and loss of connectivity will result.
198 Chapter 6: Using OSPF in a Single Area
Figure 6-4 The Stages of Updating the Routers About the Network
OSPF Operation in a Single Area 199
The synchronization of the topology maps is ensured by the intricate use of sequence numbers in the LSA headers.
From the topology map, a routing database is constructed. This database will be unique to each router, which creates a routing database by running the shortest path first (SPF) algorithm called the Dijkstra algorithm. Each router uses this algorithm to determine the best path to each network and creates an SPF tree on which it places itself at the top, or root. If there are equal metrics for a remote network, OSPF includes all the paths and load balances the routed data trafﬁc among them.
Occasionally, a link might ﬂap or go up and down. This is more common on a serial line. If this happens, it could cause many LSAs to be generated when updating the network. To prevent this from happening, OSPF introduced timers. These timers force OSPF to wait before recalculating SPF. They are conﬁgurable.
NOTE Although RFC 2328 does not state the number of multiple, equal-cost paths that can be used at the same time, Cisco has deﬁned a maximum of six paths that can be used simultaneously for load balancing.
Maintaining the Topological Database and the Routing Table
Now turn back to the 2500 router in Building A of the San Francisco campus in Figure 6-1. The router is now happily a member of the OSPF network. This section follows the process of hearing an update to the network in the form of an LSA.
As soon as a router realizes that there has been a change in the network topology, the router is responsible for informing the rest of the routers in the area. Typically, it will identify a change in the state of one of its links for one of the following reasons:
■ The router loses the physical or data link layer connectivity on a connected network. The router propagates an LSU and sends it to the DR on a multiaccess network or the adjacent router in a point-to-point network. From there, it is ﬂooded to the network.
■ The router fails to hear either an OSPF Hello protocol or a data link Hello protocol. The router propagates an LSU and sends it to the DR on a multiaccess network or the adjacent router in a point-to-point network. From there, it is ﬂooded to the network.
■ The router receives an LSA update from an adjacent neighbor, informing it of the change in the network topology. The LSU is acknowledged and ﬂooded out the other OSPF interfaces.
In any of these instances, the router will generate an LSA and ﬂood it to all its neighbors.
This discussion now turns to the process initiated when a router receives such an update. For this purpose, return to the 2500 router connected to its DR, the 7200, in Figure 6-1.
200 Chapter 6: Using OSPF in a Single Area
Learning a New Route
When the 2500 router receives a network LSA update from the DR, it goes through the following logical steps:
1. The router takes the ﬁrst entry from the update—the ﬁrst network with information about the state of its link.
2. The router veriﬁes that the type of LSA is one that can be accepted by this router.
3. Having ascertained that it is a valid LSA which it can receive, the router issues a lookup to its topological database.
4. If the LSA entry is not in the topological database, it is ﬂooded immediately out all the OSPF interfaces, except for the receiving interface.
5. If the LSA entry is in the topological database, further questions are required.
6. The router determines whether the new LSA has a more recent (higher) sequence number.
7. If the sequence numbers are the same, the router calculates the checksum for the LSAs and uses the LSA with the higher checksum.
8. If the checksum numbers are the same, the router checks the MaxAge ﬁeld to ascertain which is the most recent update.
9. Having found that the latest LSU is the one that was received, the router determines whether it has arrived outside the wait period, before another computation is allowed (minsLSarrival).
10. If the new LSA entry passes these tests, it is ﬂooded out all the OSPF interfaces, except for the receiving interface.
11. The current copy replaces the old LSA entry. If there was no entry, the current copy is just placed in the database.
12. The received LSA is acknowledged.
13. If the LSA entry was in the database, but the LSA that has just been received has an older sequence number, the router asks whether the information in the database is the same.
14. If the information is the same and the new LSA has an older sequence number, the process discards the packet. It might be old news, but there is no inconsistency in the database.
15. If the information is different and the newly received LSA has an older sequence number, however, the receiving router discards the LSA update. It issues a copy of the LSA it has in its database, sending it out of the receiving interface to the source address of the out-of-date LSA. The logic is that the sending router has bad or old information and must be updated because its topological database is obviously not synchronized with the rest of the area.
OSPF Operation in a Single Area 201
This ensures that any packets that get out of sequence will be veriﬁed before action is taken. It also attempts to rectify a problem that it sees—that of multiple routers offering different paths because their topological databases are completely confused.
16. After the initial ﬂood, things calm down, and updates are sent only when there are changes in the area or when the 30-minute timer goes off. This timer ensures that the databases stay synchronized.
This process shows some of the internal complexity of OSPF. As you can see, the internals are extremely detailed. Therefore, the design of any OSPF network should be very carefully thought out. The conﬁguration of the routing protocol, on the other hand, is incredibly straightforward.
Choosing the Shortest Path First and Building the Routing Table
As with any routing protocol, OSPF examines all the available paths to every network that it knows about. It selects the shortest, most direct path to that destination. This section discusses the metric OSPF uses to select the shortest path and the routing table information needed after the shortest path is determined.
As with all routing protocols, the decision as to which path to place into the routing table is based on the metric used by the routing protocol. RIP, for example, uses hop count, which shows how many routers must be passed through to get to the destination. When CPU and memory speeds were slower, the latency of traveling through the router had much higher implications on network performance. OSPF has few of those constraints and so chooses the metric of cost. Cost is not deﬁned, however; it depends on the implementation of the protocol. The metric can be programmed to be either complex or simple. Cisco’s implementation of a dynamic and default cost uses a predeﬁned value based on the bandwidth of the router interface. The network administrator can manually override this default.
On occasion, the metric determines more than one path to the destination. These are known as multiple equal-cost paths.
The cost is applied to the outgoing interface. The routing process will select the lowest accumulated cost of the interfaces to the remote network.
Information Needed in the Routing Table
Having determined the shortest path or multiple equal-cost paths, the routing process will need to supply additional information. To forward the data down the chosen path, the next logical hop, link, and outgoing interface must be ascertained. The routing table, or forwarding database, as it is sometimes called, requires this information.
The operation of OSPF across WANs is slightly different. The next section considers OSPF used over these different technologies.