This tutorial explains OSPF Metric calculation formula and SPF algorithm step by step in detail with examples. Learn how SPF (Shortest Path First) algorithm calculates cumulative cost of route to build the Shortest Path Tree (SPT) and how OSPF Metric Formula can be manipulated by changing reference bandwidth value.
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.
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.
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.
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 = 10 | 10 |
FastEthernet Link | 100Mbps | 100000000/100000000 = 1 | 1 |
Serial Link | 1544Kbps(default) | 100000000/1544000 = 64.76 | 64 |
Cost of common lines
Line | Bandwidth | Metric calculation | Cost |
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 learn how SPF algorithm selects the best route from available routes.
Create a practice lab as illustrated in following figure or download this pre-created practice lab and load in practice tracer.
Download OSPF Practice Topology with OSPF configuration
Access CLI prompt of Router0.
Run show ip route ospf command from privilege mode to view all learned routes through the OSPF protocol.
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 Interface | Bandwidth | Metric Calculation | Cost |
R0 | Se0/0/1 | 1544Kbps (Default ) | 100000000/1544000 = 64.76 | 64 |
R3 | Se0/0/0 | 1544Kbps (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 = 1 | 1 |
Cumulative cost of route (1+ 1 + 1) = 3 |
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)
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)
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
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
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
Route R0 – R5 – R6 has the lowest cost value.
After selecting best route for each destination OSPF network look likes following figure.
OSPF Route cost Manipulation
We can manipulate OSPF route cost in two ways.
- By changing bandwidth of interface
- 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.
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
{module in_art_slot_10}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 = 12In 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.