OSPF Link-State Routing Protocol
OSPF is a link-state routing protocol. This means that an OSPF-speaking router exchanges detailed routing information about the state of its links through Type-1 router or Type-2 network Link State Advertisements (LSAs). These LSAs are shared in Link State Update packets among all routers in the topology and stored in the Link State Database (LSDB). When two neighbors come online, they exchange all LSAs in their LSDBs with each other, ensuring the LSDB is synchronized across all routers in a specific OSPF area.
Once the LSDB is synchronized within an area, the router can construct a graph or map of the area topology, comprising nodes and their connecting links. With complete topology information, OSPF performs a shortest-path computation to determine the shortest path to any node in the graph using the Dijkstra SPF algorithm. After executing the Dijkstra SPF algorithm on all nodes, the router builds a shortest-path tree from itself (as the root) to all other nodes in the graph. This tree provides the routes that the router installs into the routing table.
Any changes to a router’s link-state information, such as adding or removing a link, modify the area’s graph. The affected router advertises this change via an LS UPDATE packet amending its LSAs. Upon receiving this update with new Type-1 router or Type-2 network link state information, the local router must recompute its own shortest-path tree (SPT) to ensure it uses the most efficient paths within its area.
However, not all graph changes affect the local router's SPT or may only impact a portion of it. Recalculating the entire SPT in such cases could be unnecessarily CPU-intensive, especially in large OSPF areas with many routers.
For instance, consider a topology where one router is a leaf-node from another router’s perspective, meaning it doesn't connect to any other downstream routers. Another router connects the first router to the leaf-node, acting as a branch router for transiting traffic. If the branch-to-leaf link goes down, the first router doesn't need to recalculate its entire SPT to remove the leaf-node from the network edge.
This situation is addressed by the task's statement: if there is a change in Type-1 or Type-2 LSAs in an area, routers should not run a full SPF. Instead, only the affected SPT portions should be recalculated. This means that rather than recomputing the entire SPT, the router can remove the affected link with minimal effort by running a partial SPF algorithm, known as an incremental SPF calculation.
Incremental SPF Calculations
Incremental SPF calculations optimize the SPF process by differentiating between two types of calculations:
- Full SPF: Runs against the entire LSDB.
- Incremental SPF: Recalculates only the affected part of the local router’s SPT.
Full SPF calculations are triggered whenever a change is made to one of the router’s own Type-1 or Type-2 LSAs, indicating a change in one of its core links. For example, if a router loses its connection with another, it must run a full SPF to recompute its entire SPT.
Incremental SPF calculations occur in the following scenarios:
- When a leaf-node router or link goes up or down.
- When a non-SPT link goes up or down.
- When an SPT branch fails.
In the first scenario, if the link between two routers goes down, only an incremental SPF calculation is needed to remove the affected router from the SPT. The second scenario involves a topology link not used in the SPT, where a full calculation would be redundant. The third scenario involves an indirectly-connected SPT branch failure, where only the affected part of the SPT is recalculated.
Enabling Incremental SPF
The incremental SPF feature is enabled using the ispf command in OSPF router configuration mode.