Shortest Path First SPF algorithm (Dijkstra algorithm)

OSPF use SPF algorithm to calculate the shortest path between points in the network using Dijkstra algorithm. The Dijkstra SPF routing algorithm is the basis for OSPF operations.

How SPF works?
When a router is booted, it’s assured that its interfaces are up and working, then use the OSPF Hello packets to find neighbors. The router sends hello packets to its neighbors and receives their hello packets back. All routers exchange link-states by means of flooding. Each router that receives a link-state update using this router build its link state database and then propagate the update to other routers.
On multi-access environment, DR router is selected which is responsible for generating LSAs for the entire multi-access network.

When the link-state databases of two neighboring routers are synchronized, the routers are said to be adjacent. Then router uses the Dijkstra algorithm in order to calculate the shortest path tree. The destinations, the associated cost and the next hop to reach those destinations form the IP routing table.

The algorithm places each router at the root of a tree and calculates the shortest path to each destination based on cost required to reach that destination. Each router will have its own view of the topology even though all the routers will build a shortest path tree using the same link-state database.

Whenever there is a change in OSPF network, it is communicated through link-state updates, and the Dijkstra algorithm is recalculated in order to find the shortest path.

Consider the following network diagram with the indicated interface costs. Now suppose that router0 want to calculate the shortest path to router4, for this we make Router0 the root of the tree and calculate the smallest cost for its destination router4.

In network diagram you can see that Router0 have two paths to router4. One has total cost of 12(1+10+1) to reach router4 and second have a cost of 6(5+1). Router0 chose the second path as a shortest path using SPF because this path has less cost to reach. Similarly all routers in network set himself as root and calculate the shortest to destination.

OSPF Lab Examples:
OSPF DR/BDR selection By Loopback Configuration

No comments:

Post a Comment