Shortest Path First (SPF) Algorithm Explained

OSPF is a routing protocol. It uses the SPF (Shortest Path First) algorithm to calculate and select the fastest path. This tutorial explains how the SPF algorithm works and how to manipulate it.

The SPF algorithm uses the bandwidth as the metric. The bandwidth tells how fast a link is. If a link has high bandwidth, it is fast. If it has less bandwidth, it is slow. For example, a 100 Mbps Ethernet link will transfer data faster than a 56 Kbps serial link. A higher bandwidth link also has less overhead than a lower bandwidth link. Overhead directly affects the data flow on the link. Less overhead provides better data transfer speed.

SPF uses these things to calculate the cost of links. Cost is inversely proportional to bandwidth. Higher bandwidth costs less. Lower bandwidth costs more. It uses the following formula to calculate the link cost.

Cost = Reference bandwidth / Interface bandwidth in bps

RFC 2338 defines the reference bandwidth as an arbitrary value. Vendors need to use their reference bandwidth. Cisco uses 100Mbps (108) bandwidth as the reference bandwidth. On Cisco routers, it will use the following formula.

Cost = 108/interface bandwidth in bps

When using the above formula, you need to consider the following things.

  • Cost is a positive integer value.
  • If you get the cost in decimal, you must convert it into the nearest positive integer.
  • If you get the cost smaller than one, you will use one as the cost.

SPF calculation examples

Line/Interface Type Bandwidth Actual cost Final cost
Ethernet Link 10Mbps 100000000/10000000 = 10 10
FastEthernet Link 100Mbps 100000000/100000000 = 1 1
Serial Link 1544Kbps(default) 100000000/1544000 = 64.76 64
56 Kbps line 56Kbps 100000000/56000 = 1785.71 1785
64 Kbps line 64Kbps 100000000/64000 = 1562.5 1562
128 Kbps line 128Kbps 100000000/128000 = 781.25 781
512 Kbps line 512 Kbps 100000000/512000 = 195.31 195
1 Mbps line 1Mbps 100000000/1000000 = 100 100
10 Mbps line 10Mbps 100000000/10000000 = 10 10
100 Mbps line 100Mbps 100000000/100000000 = 1 1
1 Gbps line 1Gbps 100000000/1000000000= 0.1 1
10 Gbps line 10Gbps 100000000/10000000000 = 0.01 1

SPT (Shortest Path Tree)

SPT (Shortest Path Tree) is a database of the shortest path for every destination. The router creates the SPT database in the following three steps.

  • It learns all available paths for every destination.
  • It runs the SPF algorithm on all paths to calculate the cost of all paths.
  • It selects the path having the least cost for every destination and adds it to the routing table.

A destination may have multiple paths. A path can have multiple links. If it has more than one link, it uses the cumulative cost. A cumulative cost is the sum of all outgoing interfaces' costs in the path. It uses only the cost of the outgoing interfaces to calculate the cumulative cost. It does not include the cost of incoming interfaces.

SPF metric calculation Packet Tracer example

Create a packet tracer or GNS3 lab, as shown in the following image.

packet tracer

Assign IP configurations shown in the above image and configure the OSPF routing protocol on all routers.

Download Packet Tracer LAB with IP configuration and OSPF Routing

R1 has two routes to reach the networks 40.0.0.0/8 and 50.0.0.0/8. Run the show ip route opsf command on R1 to view both routes.

show ip route

Let us understand why R1 picks the above routes for these networks.

Network 40.0.0.0/8

R1 has the following routes to reach this network.

Route1
Router Exit interface Default link bandwidth Actual cost Final cost
R1 GigE0/0 1Gbps 100000000/1000000000= 0.1 1
R2 GigE0/1 1Gbps 100000000/1000000000= 0.1 1
The cumulative cost of the Route1 = 1 + 1 2
Route2
Router Exit interface Default link bandwidth Actual cost Final cost
R1 Serial0/0/0 1544Kbps 100000000/1544000 = 64.76 65
R3 GigE0/1 1Gbps 100000000/1000000000= 0.1 1
The cumulative cost of the Route1 = 65 + 1 66

Since the cumulative cost of Route1 is less than the cumulative cost of Route2, it will use Route1 to reach the network 40.0.0.0/8.

Network 50.0.0.0/8

R1 has the following routes to reach this network.

Route1
Router Exit interface Default link bandwidth Actual cost Final cost
R1 GigE0/0 1Gbps 100000000/1000000000= 0.1 1
R2 GigE0/1 1Gbps 100000000/1000000000= 0.1 1
R3 GigE0/2 1Gbps 100000000/1000000000= 0.1 1
The cumulative cost of the Route1 = 1 + 1 + 1 3
Route2
Router Exit interface Default link bandwidth Actual cost Final cost
R1 Serial0/0/0 1544Kbps 100000000/1544000 = 64.76 65
R3 GigE0/2 1Gbps 100000000/1000000000= 0.1 1
The cumulative cost of the Route1 = 65 + 1 66

Since the cumulative cost of Route1 is less than the cumulative cost of Route2, it will use Route1 to reach the network 50.0.0.0/8.

Manipulating the SPF algorithm

As we know, the SPF algorithm uses bandwidth as the metric. By manipulating the default bandwidth, we can change the result of the SPF algorithm.

In the preceding example, R1 takes Route1 to reach the network 50.0.0.0/8. Now, suppose we want it to take Route2 instead of Route1. For this, we have to manipulate the default bandwidth of Route2.

Route2 has a serial (cost 65) and an Ethernet (cost 1) link. If we want R1 to take this route, we will change the serial link's bandwidth. We use the bandwidth command in interface configuration mode to change the bandwidth. This command takes the in Kbps.

Change the serial interface's bandwidth on R1 and run the "show ip route opsf" command again.

change bandwidth

As we can see in the above output, R1 has changed the default route for the network 50.0.0.0/8 to Route2.

Download Packet Tracer LAB with manipulated SPF algorithm

The bandwidth command

The bandwidth command changes an interface's bandwidth only on the running configuration. It does not have any effect on the actual bandwidth the interface has. In other words, the bandwidth command only manipulates the bandwidth in the running configuration to influence the routing protocol that uses it as a metric component.

ComputerNetworkingNotes CCNA Study Guide Shortest Path First (SPF) Algorithm Explained