Having discussed the big picture when it comes to Link-State protocols, let’s now take a more detailed look. With IP there are two Link-State protocols in use:
- OSPF: Open Shortest Path First
- IS-IS: Intermediate System to Intermediate System
Both work in pretty much the same way, but because it’s more commonly used, for now we’ll focus on OSPF.
In an OSPF router, the topology database is referred to as the Link State Database (LSDB). The LSDB contains the detailed information that a router has regarding the topology of the internetwork. Each entry in the LSDB is called a Link State Advertisement (LSA). In OSPF, there are five packet types used:
- Hello: Used to build and maintain neighbor relationships.
- DBD: Database Description, a summary of the LSDB.
- LSR: Link State Request, used to request one or more missing LSAs.
- LSU: Link State Update, used to send one or more LSAs.
- LSAck: Link State Acknowledgement, used to acknowledge receipt of a LSU.
When a new neighbor is found, an OSPF router’s goal is to synchronize its LSDB with that of the neighbor. By “synchronize” we mean make the LSDBs consistent, so that they contain the same LSAs. To accomplish this, the routers compare LSDBs (“You show me yours, and I’ll show you mine!”) and any LSA that a router is missing it requests from the neighbor. During this process, the neighbors proceed through the following OSPF states:
- Down: The start of the neighbor process.
- Init: The neighbor relationship is being initialized.
- Two-Way: The neighbor relationship has been confirmed.
- Exstart: The routers negotiate which sends its DBD first.
- Exchange: The DBDs are being exchanged.
- Loading: The LSRs and LSUs are being exchanged.
- Full: The LSDBs are synchronized.
Once the LSDB is complete, a router runs the Shortest Path First (SPF) algorithm, generating its routing table. In OSPF the metric is cost, and SPF finds the lowest cost path to each destination prefix. Note that SPF is where OSPF gets its name: it’s an “Open” (non-proprietary) protocol that uses SPF. The SPF algorithm is commonly referred to as “Dijkstra’s Algorithm”, after Edsger Dijkstra (pronounced Dike-stra), the computer scientist who developed it.
After the routing tables have been generated, the network is converged. The goal is to maintain full state (LSDB synchronization) with the neighbors. Let’s say that router R1 senses a topology change, such as gaining or losing a link. It will then update the R1 LSA in its LSDB, flood a copy of the revised R1 LSA to its neighbors, and run SPF to regenerate its routing table. R1’s neighbors will acknowledge receipt of R1’s revised LSA, replace the old R1 LSA in their LSDBs with the new R1 LSA, flood the new R1 LSA to their neighbors, and run SPF. In this manner, the new R1 LSA propagates throughout the internetwork, and as it does it updates the LSDB, triggers SPF, and regenerates the routing table of each router. Once this process is complete (and it typically takes only seconds) routing is again converged.
LSUs are sent only when changes occur (that is, they’re triggered updates), so in between LSUs a router sends periodic Hellos to reassure its neighbors of its continued presence. Since Hellos are small, they don’t take much bandwidth or CPU power to process, and can be sent relatively frequently (every few seconds is typical). Because changes are only being advertised when they occur, the result is that Link-State protocols such as OSPF scale better than Distance-Vector protocols like RIP, which periodically flood the entire routing table even in the absence of any changes.
Next time, we’ll look at some additional details and enhancements regarding OSPF.
Author: Al Friebe