CCNA Study Guide

OSPF uses SPF (Shortest Path First) algorithm to select the best route for routing table. SPF algorithm was invented in 1956 by Edsger W. Dijkstra. It is also referred as Dijkstra algorithm. SPF is a quite complex algorithm. In this tutorial we will explain a simplified overview of this algorithm.

This tutorial is the last part of our article “OSPF Routing Protocol Explained with examples". You can read other parts of this article here.

OSPF Fundamental Terminology Explained

This tutorial is the first part of this article. In this part we explained basic terminology of OSPF such as Feature , Advantage and Disadvantage, Autonomous System, Area concept, ABR, IR, Link, State ,LSA and LSDB with example.

OSPF Neighborship Condition and Requirement

This tutorial is the second part of this article. OSPF neighborship is built between two routers only if configuration value of Area ID, Authentication, Hello and Dead interval, Stub Area and MTU are matched. This part explains these parameters and OSPF adjacency in detail with examples.

OSPF Neighbor States Explained with Example

This tutorial is the third part of this article. OSPF adjacency process goes through the seven states; OSPF State down, OSPF State Init, OSPF State two ways, OSPF State Exstart, OSPF State Exchange, OSPF State Loading and OSPF State full. This part explains these states with DR BDR selection process in detail with examples.

OSPF Configuration Step by Step Guide

This tutorial is the fourth part of this article. Configuration part of OSPF includes process ID, Area ID and wildcard mask which make its setup a litter bit harder. This part explains these parameters in detail with examples.

Shortest Path First (SPF) Algorithm

As we know upon initialization or due to any change in routing information an OSPF router generates a LSA. This LSA (Link State Advertisement) contains the collection of all link-states on that router. Router propagates this LSA in network. Each router that receives this LSA would store a copy of it in its LSA database then flood this LSA to other routers.

To learn how this happens, please see third part of this article. In that part I explained this process in detail with examples.

After database is updated, router selects a single best route for each destination from all available routes. Router uses SPF algorithm to select the best route.

Just like other routing algorithm SPF also uses a metric component called cost to select the best route for routing table.

OSPF Metric cost

Logically a packet will face more overhead in crossing a 56Kbps serial link than crossing a 100Mbps Ethernet link. Respectively it will take less time in crossing a higher bandwidth link than a lower bandwidth link. OSPF uses this logic to calculate the cost. Cost is the inverse proportional of bandwidth. Higher bandwidth has a lower cost. Lower bandwidth has a higher cost.

OSPF uses following formula to calculate the cost

Cost = Reference bandwidth / Interface bandwidth in bps.

Reference bandwidth was defined as arbitrary value in OSPF documentation (RFC 2338). Vendors need to use their own reference bandwidth. Cisco uses 100Mbps (108) bandwidth as reference bandwidth. With this bandwidth, our equation would be

Cost = 108/interface bandwidth in bps

Key points

  • Cost is a positive integer value.
  • Any decimal value would be rounded back in nearest positive integer.
  • Any value below 1 would be considered as 1.

Now we know the equation, let’s do some math and figure out the default cost of some essential interfaces.

Default cost of essential interfaces.

Interface Type bandwidth Metric Calculation Cost
Ethernet Link 10Mbps 100000000/10000000 = 1010
FastEthernet Link 100Mbps 100000000/100000000 = 1 1
Serial Link 1544Kbps(default) 100000000/1544000 = 64.7664

Cost of common lines

Line Bandwidth Metric calculationCost
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/100000000 0= 0.1 1
10 Gbps line 10Gbps 100000000/10000000000 = 0.01 1

SPT (Shortest Path Tree)

OSPF router builds a Shortest Path Tree. SPT is just like a family tree where router is the root and destination networks are the leaves. SPF algorithm calculates the branch cost between leaves and root. Branch with lowest cost will be used to reach at leaf. In technical language route that has lowest cumulative cost value between source and destination will be selected for routing table.

Cumulative cost = Sum of all outgoing interfaces cost in route

Best route for routing table = Route which has the lowest cumulative cost

Summary

  • OSPF uses SPT tree to calculate the best route for routing table.
  • A SPT tree cannot grow beyond the area. So if a router has interfaces in multiple areas, it needs to build separate tree for each area.
  • SPF algorithm calculates all possible routes from source router to destination network.
  • Cumulative cost is the sum of the all costs of the outgoing OSPF interfaces in the path.
  • While calculating cumulative cost, OSPF consider only outgoing interfaces in path. It does not add the cost of incoming interfaces in cumulative cost.
  • If multiple routes exist, SPF compares the cumulative costs. Route which has the lowest cumulative cost will be chosen for routing table.

Now we have a basic understanding of SPF algorithm. In remaining part this tutorial we will explain how SPF algorithm selects the best route from available routes.

For demonstration purpose we will use same network topology which we have created in previous part of this article.

Following figure illustrates that network topology.

ospf cost calculation example

For this tutorial I assume that you have this configured topology.

Download OSPF Practice Topology with OSPF configuration

Load this topology in packet tracer and access CLI prompt of Router0.

Run show ip route ospf command from privilege mode to view all learned routes through the OSPF protocol.

show ip route

As output shows, Router0 has six routes from OSPF in routing table. We will go through the each route and find out why it was chosen as the best route for routing table by OSPF.

Route 20.0.0.0

We have three routes to get 20.0.0.0/8 network. Let’s calculate the cumulative cost of each route.

Via Route R0-R1-R2-R6

Router Exit Interface Bandwidth Metric Calculation Cost
R0 Se0/0/0 64Kbps ( Manually Assigned) 100000000/64000 = 1562.5 1562
R1 Se0/0/1 64Kbps ( Manually Assigned) 100000000/64000 = 1562.5 1562
R2 Se0/0/0 64Kbps ( Manually Assigned) 100000000/64000 = 1562.5 1562
R6 Fa0/1 100Mbps 100000000/100000000 = 1 1
Cumulative cost of route (1562 + 1562 + 1562 + 1) = 4687

Via route R0 – R3 – R4 – R6

Router Exit InterfaceBandwidth Metric Calculation Cost
R0 Se0/0/1 1544Kbps (Default ) 100000000/1544000 = 64.76 64
R3 Se0/0/01544Kbps (Default ) 100000000/1544000 = 64.76 64
R2 Se0/0/1 1544Kbps (Default ) 100000000/1544000 = 64.76 64
R6 Fa0/1 100Mbps 100000000/100000000 = 1 1
Cumulative cost of route (64 + 64 + 64 + 1) = 193

Via route R0 – R5 – R6

Router Exit Interface Bandwidth Metric Calculation Cost
R0 Fa0/1 100Mbps 100000000/100000000 = 1 1
R5 Fa0/0 100Mbps 100000000/100000000 = 1 1
R0 Fa0/1 100Mbps 100000000/100000000 = 11
Cumulative cost of route (1+ 1 + 1) = 3

ospf metric explained

Among these routes, route R0-R5-R6 has the lowest cumulative cost. So it was selected as the best route for routing table.

Route 192.168.0.4

Via Route R0 – R1

R0’s Serial 0/0/0 cost (1562) + R1’s Serial 0/0/1 cost (1562) = 3124 (Cumulative cost)

Via Route R0 – R3 – R4 – R6 – R2

R0’s Serial 0/0/1 cost (64) + R3’s Serial 0/0/0 cost (64) + R4’s Serial 0/0/1 cost (64) + R6’s Serial 0/0/0 cost (64) + R2’s Serial 0/0/1 cost (64) = 320 (Cumulative cost)

Via Route R0 – R5 – R6 – R2

Ro’s FastEthernet 0/1 cost (1) + R5’s FastEthernet 0/0 cost (1) + R6’s Serial 0/0/0 cost (64) +R2’s Serial 0/0/1 cost (64) = 130 (Cumulative cost)

ospf metric

Among these routes, Route R0 – R5 – R6 – R2 has the lowest cost so it was picked for routing table.

Route 192.168.0.8

Via Route R0 – R1

R0’s Serial 0/0/0 cost (1562) + R1’s Serial 0/0/1 cost (1562) + R2’s Serial 0/0/0 (1562) = 4686 (Cumulative cost)

Via Route R0 – R3 – R4 – R6

R0’s Serial 0/0/1 cost (64) + R3’s Serial 0/0/0 cost (64) + R4’s Serial 0/0/1 cost (64) + R6’s Serial 0/0/0 cost (64) = 256 (Cumulative cost)

Via Route R0 – R5 – R6

Ro’s FastEthernet 0/1 cost (1) + R5’s FastEthernet 0/0 cost (1) + R6’s Serial 0/0/0 cost (64) = 66 (Cumulative cost)

ospf bandwidth metric

Among these routes, Route R0 – R5 – R6 has the lowest cost so it was picked for routing table.

Route 192.168.1.4

Via Route R0 – R1 – R2 – R6

R0’s Serial 0/0/0 cost (1562) + R1’s Serial 0/0/1 (1562) + R2’s Serial 0/0/0 (1562) + R6’s FastEthernet 0/0 (1) = 4687 (Cumulative cost)

Via R0 – R3 – R4 – R6

R0’s Serial 0/0/1 cost (64) + R3’s Serial 0/0/0 cost (64) + R4’s Serial 0/0/1 cost (64) + R6’s FastEthernet 0/0 (1) = 193

Via R0 – R5

R0’s FastEthernet 0/1 cost (1) + R5’s FastEthernet 0/0 cost (1) = 2

ospf spf algorithm example

Among these routes, Route R0 – R5 has the lowest cost so it was selected as the best route.

Route 192.168.2.4

Via Route R0 – R1 – R2 – R6 – R4

R0’s Serial 0/0/0 cost (1562) + R1’s Serial 0/0/1 cost (1562) + R2’s Serial 0/0/0 cost (1562) + R6’s Serial 0/0/1 cost (64) + R4’s Serial 0/0/0 cost (64) = 4814

Via Route R0 – R5 – R6 – R4

R0’s FastEthernet 0/1 cost (1) + R5’s FastEthernet 0/0 cost (1) + R6’s Serial 0/0/1 (64) + R4’s Serial 0/0/0 cost (64) = 130

Via Route R0 – R3

R0’s Serial 0/0/1 cost (64) + R3’s serial 0/0/0 cost (64) = 128

ospf metric cost calculation

Among these routes, Route R0 - R3 has the lowest cost for destination 192.168.2.4.

Route 192.168.2.8

Via Route R0 – R3 – R4

R0’s Serial 0/0/1 cost (64) + R3’s Serial 0/0/0 cost (64) + R4’s Serial 0/0/1 cost (64) = 192

Via Route R0 – R1 – R2 – R6

Ro’s Serial 0/0/0 cost (1562) + R1’s Serial 0/0/1 cost (1562) + R2’s Serial 0/0/0 cost (1562) + R6’s Serial 0/0/1 cost (64) = 4750

Via Route R0 – R5 – R6

R0’s FastEthernet 0/1 cost (1) + R5’s FastEthernet 0/0 cost (1) + R6’s Serial 0/0/1 cost (64) = 66

how ospf metric calculated

Route R0 – R5 – R6 has the lowest cost value.

After selecting best route for each destination OSPF network look likes following figure.

ospf spf example

OSPF Route cost Manipulation

We can manipulate OSPF route cost in two ways.

  1. By changing bandwidth of interface
  2. By changing reference bandwidth value

By changing bandwidth of interface

Sub interface mode command Bandwidth is used to set the bandwidth of supported interface.

If bandwidth is set through this command, OSPF will use it. If bandwidth is not set, it will use interface’s default bandwidth.

When we enable an interface, router automatically assign a bandwidth value to it based on its type. For example serial interface has a default bandwidth value of 1544k. Until we change this value with bandwidth command, it will be used where it is required.

Let me clear one more thing about bandwidth. Changing default bandwidth with bandwidth command does not change actual bandwidth of interface. Neither default bandwidth nor bandwidth set by bandwidth command has anything to do with actual layer one link bandwidth.

Then what purpose does this command solve?

This command is only used to influence the routing protocol which uses bandwidth in route selection process such as OSPF and EIGRP.

We have already seen an example of this method in our example. We changed default bandwidth (1544Kbps) to custom (64kbps) bandwidth on R0’s serial 0/0/0, R1’s serial 0/0/1 and R2’s serial 0/0/0. Due to this change R0 took another router for 192.168.0.4 network.

Let’s understand this in more detail.

Current cost for destination 192.168.0.4 from R0

Via Route R0 – R1

R0’s Serial 0/0/0 cost (1562) + R1’s Serial 0/0/1 cost (1562) = 3124 (Cumulative cost)

Via Route R0 – R5 – R6 – R2

Ro’s FastEthernet 0/1 cost (1) + R5’s FastEthernet 0/0 cost (1) + R6’s Serial 0/0/0 cost (64) +R2’s Serial 0/0/1 cost (64) = 130 (Cumulative cost)

Via Route R0 – R3 – R4 – R6 – R2

R0’s Serial 0/0/1 cost (64) + R3’s Serial 0/0/0 cost (64) + R4’s Serial 0/0/1 cost (64) + R6’s Serial 0/0/0 cost (64) + R2’s Serial 0/0/1 cost (64) = 320 (Cumulative cost)

Among these routes, Route R0 – R5 – R6 – R2 has the lowest cost so it was picked for routing table.

Well … Which route would have selected, if we had used default bandwidth?

Cost for destination 192.168.0.4 from R0 with default bandwidth.

Via Route R0 – R1

R0’s Serial 0/0/0 cost (64) + R1’s Serial 0/0/1 cost (64) = 128 (Cumulative cost)

Via Route R0 – R5 – R6 – R2

Ro’s FastEthernet 0/1 cost (1) + R5’s FastEthernet 0/0 cost (1) + R6’s Serial 0/0/0 cost (64) +R2’s Serial 0/0/1 cost (64) = 130 (Cumulative cost)

Via Route R0 – R3 – R4 – R6 – R2

R0’s Serial 0/0/1 cost (64) + R3’s Serial 0/0/0 cost (64) + R4’s Serial 0/0/1 cost (64) + R6’s Serial 0/0/0 cost (64) + R2’s Serial 0/0/1 cost (64) = 320 (Cumulative cost)

Among these routes, Route R0 – R1 has the lowest cost value so it would be selected for routing table. Thus by changing interface bandwidth we actually influenced route selection process.

By changing reference bandwidth value

As I mention earlier, by default OSPF uses 100Mbps bandwidth as a reference bandwidth. Changing this value would also change the cost of route. If we use 1000Mbps as a reference bandwidth, cost of 100Mbps link would become 10. This sounds great, especially if we have higher bandwidth links in our network. For example have a look on following figure.

ospf auto refference command example

Which route will R2 take to get the network of 10.0.0.0/8?

Route R2 – R3

In this route we have two exit points. Both points have default 1oo Mbps speed.

R2’s FastEthernet cost (100000000/100000000) = 1

R3’s FastEthernet cost (100000000/100000000) = 1

Cost of this route 1 + 1 = 2

Route R2 – R1 – R3

In this route we have three exit points. Two exit points (R2 and R1) have 1 Gbps link.

R2’s FastEthernet cost (100000000/1000000000) = .1 (Anything below 1 would be considered as 1)

R3’s FastEthernet (100000000/1000000000) = .1 (Anything below 1 would be considered as 1)

R3’s FastEthernet cost (100000000/100000000) = 1

Cost of this route 1 + 1 + 1 = 3

With default reference bandwidth R2 will choose Route R2 – R3, which is not good.

We can adjust reference bandwidth with auto-cost reference-bandwidth ref-band command.

We need to adjust reference bandwidth on all routers of network. Mismatched reference bandwidth can cause routers to run the SPF algorithm continually, which could create a serious performance issue.

Reference bandwidth is assigned in Mbps. Valid range is 1 to 4294967. Default reference bandwidth is 100Mbps.

Sadly packet tracer does not include this command. For the practice of this command please use other simulator software which support this command or use real router.

Let’s change reference bandwidth to 1000Mbps on all three routers using following commands

Router# configure terminal
Enter configuration commands, one per line.  End with CNTL/Z.
Router (config)#router ospf 1
Router (config-router)#auto-cost reference-bandwidth 1000
% OSPF: Reference bandwidth is changed.
        Please ensure reference bandwidth is consistent across all routers.
Router (config-router)#exit
Router #

Route cost with new reference bandwidth

Route R2 – R3

R2’s FastEthernet cost (1000000000/100000000) = 10

R3’s FastEthernet cost (1000000000/100000000) = 10

Cost of this route 10 + 10 = 20

Route R2 – R1 – R3

R2’s FastEthernet cost (1000000000/1000000000) = 1

R3’s FastEthernet (1000000000/1000000000) = 1

R3’s FastEthernet cost (1000000000/100000000) = 10

Cost of this route 1 + 1 + 10 = 12

In this case Route R2-R1-R3 will be selected, which is the shortest route for destination.

That’s all for this article. I hope now you have better understanding of OSPF Routing protocol. In next article I will explain Access List in detail with examples.

Improve this articleImprove this article

Thanks for reading this article. We believe that every article always has a scope for improvement. Following this principle we invite you to update this article. Your little effort and time will make this article more useful for other users. You can improve this article in two ways.

Improve this articleTechnical update

  • Update outdated or incorrect information
  • Add missing or relative information
  • Make this easier to understand

Improve this articleLanguage update

  • Use more simple words for presentation
  • Correct spelling errors and typos
  • Update grammatical mistakes

Please download editable version of this article in DOCX format and send updated version back to computernetworkingnotes@gmail.com

Share this Share This Article with Friends

Stay updateStay Update With US

More Articles For YouYou May Also Like