Introduction to Shortest Path First Protocol

Shortest path first protocol also known as Link-state routing protocols using Edsger Dijkstra’s shortest path first (SPF) algorithm. Open Shortest Path First (OSPF) and Intermediate System-to-Intermediate System (IS-IS) the two commonly used link-state routing protocols. Link-state routing protocols have more complex than the distance vector routing protocol. But, the basic functionality and configuration of link-state routing protocols are just as a sample. We can configure the basic Open Shortest Path First (OSPF)  routing protocol using the following command.

Router(config)#router ospf <process-id>

Router(config-router)#network <network ID>

Dijkstra’s Algorithm

Dijkstra’s algorithm was published in 1959 and the name of the creator was Edsger Dijkstra so it named after its creator.  OSPF(Open Shortest Path First) and IS-IS (Intermediate System-to-Intermediate System )protocols use Dijkstra’s algorithm to calculate the best path for a source to destination. The Dijkstra’s algorithm is usually referred to as the shortest path first (SPF) algorithm. The algorithm uses the addition of cost besides each path, from source to destination; to determine the total cost of a route. The route with the lowest cost has considered the best route and route with the highest cost has considered the worst route.

Shortest Path First Protocol (SPF) Example

In the figure below, the link between each router has labeled with cost value. There are three paths for R1 LAN to R6 LAN and vice versa. As shown in the figure the lowest cost is 37, so this is the shortest path sending date between LAN R1 and LAN R6. Each router containing SPF (Shortest path first) Algorithm determines its own cost to each destination in the topology.

If you notice that path 2 has a least in hop count, but the shortest path is path 3; because the cost to reach R2 to R5 is 20 and higher than the cost from R2 to R5 through R4 which is 11.