SPF explained in a Nutshell

The SPF algorithm creates a shortest-path tree to all hosts in an area or in the network backbone, with the router that is performing the calculation at the root of that tree. In order for the SPF algorithm to work in the correct manner, all routers in the area should have the same database information. In OSPF, this is performed via the database exchange process

The three sets that are used in the SPF calculation are:

1. Unknown
2. Tentative (TENT)
3. PATH

When the SPF algorithm initializes, all nodes, except for the root, which is also referred to as 'self', are placed in the Unknown set or list. The "root" is the router performing the SPF calculation. As SPF continues to run, nodes in the Unknown set are moved to the Tentative set beginning with the nodes directly connected to the root. The Tentative set is also commonly referred to simply as the TENT set or list.

As the router goes through the SPF calculation, the node in the TENT set or list that is closest (lowest cost) to the root is moved to the PATH or PATHS list or set. This process is repeated until all nodes are in the PATH set and the TENT list is empty and finally the shortest-path tree is built.

For example the OSPF database at router A would like below in the beginning.

Node	Cost	Next Hop
A	0	Self
B	Infinity	unknown
C	Infinity	unknown
D	Infinity	unknown

As and when the nodes move from TENT list to the PATH list the cost changes from infinity to an actual cost and the next-hop changes from unknown to a valid next hop Eg - {B,5,B}Node B reachable in cost 5 via B

Neighbor Table looks like below for each router

Router	{neighbor, cost} Pairs
A	{B,5} {C,10}
B	{A,5} {C,3} {D,8}
C	{A,10} {B,3} {D,4}
D	{B,8} {C,4}

Step 1. R1 places itself in the PATH list with a next-hop of itself and a cost of 0. When R1 places itself in the PATH list, R1 is also referred to as the PATH node, in addition to being the SPF root. All other nodes or routers are temporarily placed in the Unknown set and have their cost presently set to infinity

This means that Router A's databases look like

PATH List	TENT List
{A,0,0}	(empty)

Step 2. Take the node just placed on the PATH list, and call it the PATH node. Look at that node's neighbor list. Add each neighbor in this list to the TENT list with a next hop of the PATH node

Router	{neighbor, cost} Pairs
A	{B,5} {C,10}
B	{A,5} {C,3} {D,8}
C	{A,10} {B,3} {D,4}
D	{B,8} {C,4}

 

In this example, {B,5,B} and {C,10,C} get added to the TENT list, as reflected.

PATH List	TENT List
{A,0,0}	{B,5,B}
	{C,10,C}

Step 3. Find the neighbor in the TENT list with the lowest cost, add that neighbor to the PATH list, and repeat Step 2. If the TENT list is empty, stop.

{B,5,B} is moved to the PATH list, because that's the shortest path to B. Why does it thinks that B has the shortest cost? - Because {C,10,C} is the only other neighbor of Router A, and the cost to get to C is greater than the cost to get to B, it's impossible to ever have a path to B that has a lower cost than what's already known

PATH List	TENT List
{A,0,0}	{C,10,C}
{B,5,B}

Step 4. Repeat Step 2. Take the node just placed on the PATH list and call it the PATH node. Look at that node's neighbor list. Add each neighbor in this list to the TENT list with a next hop of the PATH node, unless the neighbor is already in the TENT or PATH list with a lower cost. If the node just added to a TENT list already exists in the list, but with a higher cost, replace the higher-cost node with the node currently under consideration.

Router	{neighbor, cost} Pairs
A	{B,5} {C,10}
B	{A,5} {C,3} {D,8}
C	{A,10} {B,3} {D,4}
D	{B,8} {C,4}

 Router B's neighbors are examined.

Router B has a link to C with a cost of 3 and a link to D with a cost of 8.

Router C, with a cost of 5 (to get from "self" to B) + 3 (to get from B to C) = 8 (the total cost from A to C via B) and a next hop of B, is added to the TENT list, as is Router D, with a cost of 5 (the cost to get from the root node to B) + 8 (the cost to get from B to D) = 13 and a next hop of B.

Because the path to C with a cost of 8 through B is lower than the path to C with a cost of 10 through C, the path to C with a cost of 10 is removed from the TENT list. the PATH and TENT lists at this point.

PATH List	TENT List
{A,0,0}	{C,10,C}
{B,5,B}	{C,8,B}
	{D,13,B}

Step 5.Find the path in the TENT list with the lowest cost, add that path to the PATH list, and repeat Step 2. If the TENT list is empty, stop.

The path to C through {C,8,B} is moved from the TENT list to the PATH list, as reflected in

PATH List	TENT List
{A,0,0}	{D,13,B}
{B,5,B}
{C,8,B}

Step 6. Take the path just placed on the PATH list, and look at that node's neighbor list. For each neighbor in this list, add the path to that neighbor to the TENT list, unless the neighbor is already in the TENT or PATH list with a lower cost. If the node just added to a TENT list already exists in the list, but with a higher cost, replace the higher-cost path with the path currently under consideration.

Router	{neighbor, cost} Pairs
A	{B,5} {C,10}
B	{A,5} {C,3} {D,8}
C	{A,10} {B,3} {D,4}
D	{B,8} {C,4}

 Under this rule, the path to D through B (which is really B->C->D) with a cost of 12 replaces the path to D through B->D with a cost of 13, as reflected

PATH List	TENT List
{A,0,0}	{D,13,B}
{B,5,B}	{D,12,B}
{C,8,B}

Step 7. Find the neighbor in the TENT list with the lowest cost, add that neighbor to the PATH list, and repeat Step 2. If the TENT list is empty, stop.

The path to D is moved to the PATH list, as reflected

PATH List	TENT List
{A,0,0}
{B,5,B}
{C,8,B}
{D,12,B}

Step 8. Find the neighbor in the TENT list with the lowest cost, add that neighbor to the PATH list, and repeat Step 2. If the TENT list is empty, stop.

The TENT list is empty because D has no neighbors that are not already on the PATH list, so you stop. At this point, the PATH list becomes A's routing table, which looks like

Node	Cost	Next Hop
A	0	Self
B	5	B (directly connected)
C	8	B
D	12	B

So that's how the basic SPF algorithm works. After it's done, the topology (according to Router A's routing table) looks like below: