Introduction to Shortest Path First Protocol (SPF)

The shortest path first protocol, or Link-state routing protocol, uses Edsger Dijkstra’s shortest path first (SPF) algorithm. Open Shortest Path First (OSPF) and Intermediate System-to-Intermediate System (IS-IS) are commonly used link-state routing protocols. Link-state routing protocols are more complex than the distance vector routing protocol. However, their basic functionality and configuration are just 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 creator’s name was Edsger Dijkstra, so it was 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. Dijkstra’s algorithm is usually called the shortest path first (SPF) algorithm. The algorithm uses the addition of cost beside each path, from source to destination, to determine the total cost of a route. The route with the lowest price is considered the best route, and the route with the highest cost is regarded as the worst.

Shortest Path First Protocol (SPF) Example

The link between each router is labelled in the figure below with a cost value. There are three paths from R1 LAN to R6 LAN and vice versa. The figure shows that the lowest cost is 37, so this is the shortest path for sending data between LAN R1 and LAN R6. Each router containing the SPF (Shortest path first) Algorithm determines its own cost to each destination in the topology.

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