OSPF Dynamic Routing · Topic 6 of 8

The SPF Calculation and Shortest Path Tree

Learn how OSPF builds a shortest path tree from the link state database with the SPF algorithm, how costs add up, and what triggers a new calculation.

  • 5 min
In a nutshell
  • SPF is Dijkstra's algorithm, run on the link state database.
  • Every router builds its own tree with itself at the root.
  • Routers in one area share an identical database.

What it is

The SPF calculation turns the link state database into a shortest path tree, with the calculating router at the root.

SPF stands for shortest path first. The algorithm behind it is known as Dijkstra's algorithm. Each router runs it on its own copy of the database.

Because every router in an area holds the same database, all routers agree on the map. Each one still gets a different tree, because each one is the root of its own.

Databasesame in the arearun SPFTreeroot is this routeradd networksRoutesrouting table

How it works

The router grows a tree outward from itself, always adding the closest unused router next.

The inputs

The database holds router LSAs and network LSAs. A router LSA lists the links of one router with their costs. A network LSA names the routers on a shared segment.

Together they form a graph. Routers and shared segments are the points, and the links with their costs are the lines.

The steps

The calculation follows a simple pattern.

  1. Put this router at the root of the tree with a cost of zero.
  2. Look at the links of the routers already in the tree, and compute the cost of reaching each neighbour through them.
  3. Pick the closest router that is not yet in the tree, and add it.
  4. Repeat from step 2 until all routers are in the tree.

When two paths reach the same router, the one with the lower total cost is kept. If the totals are equal, both can stay, which gives equal cost multi path.

R1root, cost 0cost 10R2total 10cost 10R4total 20R1cost 15R3total 15cost 10R4

In this example R4 can be reached through R2 at a total of 20, or through R3 at a total of 25. The tree keeps the path through R2.

Adding networks

After the routers are in the tree, the networks attached to them are added as leaves. The cost to a network is the cost to its router plus the cost of the link to the network.

Networks in other areas come from summary LSAs. The cost is the cost to the area border router plus the metric in the summary. External networks come from external LSAs, and follow the rules of their metric type.

The best paths become routes in the routing table. Each route has the next hop that leads along the path.

Costs along the path

The cost of a link counts in the direction away from the root. The cost of the outgoing interface is used at each hop. So the cost from A to B can differ from the cost from B to A, when the two interfaces have different costs.

This is how asymmetric routing can appear in OSPF. It is not a fault, but it can surprise people who test with ping.

When SPF runs

A router recalculates whenever the database changes in a way that affects the topology. A new link, a failed link or a changed cost all trigger it.

OSPF implementations normally delay the calculation briefly, so that a burst of changes causes one run and not many. If a link keeps flapping, the router recalculates often. That is one reason to use areas, because a change in one area does not trigger SPF in the others for intra area detail.

Summary and external changes cause a lighter update, because only the leaves change. The tree of routers is unchanged.

Verifying

/routing ospf lsa print
/ip route print
/routing ospf neighbor print

The routes learned through OSPF show the total cost and the next hop that SPF chose. If a route is missing, check that the LSA for it is in the database.

Exam tip

When a path is not the one you expected, add up the outgoing interface costs along both paths by hand. The router did the same sum.

What to remember for the exam

Seven facts cover most questions on this topic.

  • SPF is Dijkstra's algorithm, run on the link state database.
  • Every router builds its own tree with itself at the root.
  • Routers in one area share an identical database.
  • The path cost is the sum of the outgoing interface costs.
  • Equal cost paths can both be used.
  • Networks are added to the tree as leaves after the routers.
  • Topology changes trigger a new run, and areas limit how far a change spreads.
Watch out

The cost counts the outgoing interface only. Setting the cost on one side of a link affects traffic in one direction.

Common mistakes

These four errors appear often.

Setting the cost on one end only. Traffic in the other direction still uses the old cost, so the paths become asymmetric.

Expecting all routers to have the same tree. The database is the same, but each router is the root of its own tree.

Ignoring equal cost paths. When two paths tie, traffic is shared between them, which can surprise a tester.

Blaming SPF for a missing route. If the LSA is not in the database, the algorithm never sees the network.

Check yourself

Work through these three questions.

  • What does the SPF calculation produce?

    It produces a shortest path tree with the calculating router at the root. The networks on the tree become routes.

  • How is the cost of a path worked out?

    The costs of the outgoing interfaces along the path are added up. The lowest total wins, and equal totals can share traffic.

  • What triggers a new SPF run?

    A change in the topology, such as a new link, a failed link or a changed cost. Areas limit how far such a change spreads.

Topic 6 of 8 in OSPF Dynamic Routing

Test yourself on OSPF Dynamic Routing

The full MikroTik MTCRE question bank has 417 questions, with timed practice exams and an explanation for every answer.

SubscribeTry Sample Exam

This study guide is independent and is not affiliated with, endorsed by, or sponsored by MikroTik. Vendor names, certification names and exam codes are trademarks of their respective owners and are used for identification only.