Shortest Path First (SPF) Algorithm Explained

OSPF routing protocol uses the SPF (Shortest Path First) algorithm to calculate and select the fastest path. The SPF algorithm uses the bandwidth as the metric. The bandwidth tells how fast a link is. If a link has high bandwidth, it will be fast. If it has less bandwidth, it will be 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. Lower overhead results in faster data transfer speeds.

Cost = Reference bandwidth / Interface bandwidth in bps

RFC 2338 defines the reference bandwidth as an arbitrary value. Vendors use their own reference bandwidth. Cisco uses 100Mbps (10⁸) bandwidth as the reference bandwidth. Cisco routers use the following formula to calculate the cost.

Cost = 108/interface bandwidth in bps

Key points:-

• Cost is a positive integer value.
• If the calculated cost is in decimal, it converts that into the nearest positive integer.
• If the calculated cost is smaller than one, it uses one as the cost.

SPF calculation examples

SPT (Shortest Path Tree)

SPT (Shortest Path Tree) is a database of the shortest path for all destinations. The router creates the SPT database using 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 calculates the cumulative cost using only the cost of the outgoing interfaces. It does not include the cost of incoming interfaces.

SPF metric calculation example

Create a Packet Tracer lab as shown in the following image.

Assign IP configurations as shown in the above image and configure the OSPF routing protocol on all routers. Alternatively, you can download a prebuilt lab from the following link.

Download Packet Tracer LAB with IP configuration and OSPF Routing.

Understanding the SPF algorithm

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 to view both routes.

Network 40.0.0.0/8

R1 has the following routes to reach this network.

Route1

Route2

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

Route2

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

The SPF algorithm uses bandwidth as the metric. By manipulating the default bandwidth, you can change the result of the SPF algorithm.

In the preceding example, R1 takes Route1 to reach the network 50.0.0.0/8. If you want it to take Route2 instead of Route1, manipulate the default bandwidth of Route2. Route 2 has a serial link (cost 65) and an Ethernet link (cost 1). Change the bandwidth of the serial link. Use the bandwidth command in interface configuration mode to change the bandwidth. This command takes an input in Kbps. Change the serial interface's bandwidth on R1 and run the show ip route ospf command again.

Router>enable
Router#configure terminal
Router(config)#interface serial 0/0/0
Router(config-if)#bandwidth 1000000
Router(config-if)#exit
Router(config)#exit
Router#show ip route ospf

The output of the show ip route ospf command verifies that R1 has changed the default route for the network 50.0.0.0/8 to Route2. The following link provides the updated lab.

Download Packet Tracer LAB with a manipulated SPF algorithm.

The bandwidth command

The bandwidth command changes an interface's bandwidth only in the running configuration. It does not affect 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.

Conclusion

SPF is an algorithm. It calculates the cost of all connected links. It uses bandwidth as the metric. OSPF uses it to determine the best paths for data transmission. The cost is proportional to bandwidth. Understanding the concepts of link costs is essential when configuring OSPF in a network. Furthermore, the ability to manipulate link bandwidth can directly influence routing decisions, allowing for flexibility in network design.